Submission #3528202
Source Code Expand
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
#define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
#define debug(x) cout<<#x<<"="<<x<<endl
#define fi first
#define se second
#define mk make_pair
#define pb push_back
typedef long long ll;
using namespace std;
void File(){
freopen("gkk.in","r",stdin);
freopen("gkk.out","w",stdout);
}
template<typename T>void read(T &_){
T __=0,mul=1; char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')mul=-1;
ch=getchar();
}
while(isdigit(ch))__=(__<<1)+(__<<3)+(ch^'0'),ch=getchar();
_=__*mul;
}
const int maxn=2e5+10;
const int maxm=1e6+10;
int n,q,m;
ll f[maxn];
struct edge{
int u,v;
ll w;
bool operator < (const edge & ano) const {
return w<ano.w;
}
}E[maxm];
namespace Kruskal{
ll ans;
int fa[maxn];
int find(int x){return fa[x]==x ? x : fa[x]=find(fa[x]);}
void work(){
REP(i,0,n-1)fa[i]=i;
sort(E+1,E+m+1);
REP(i,1,m){
int u=E[i].u,v=E[i].v;
if(find(u)==find(v))continue;
fa[find(u)]=find(v);
ans+=E[i].w;
}
printf("%lld\n",ans);
}
}
int main(){
//File();
read(n); read(q);
memset(f,63,sizeof(f));
int u,v; ll w;
REP(i,1,q){
read(u),read(v),read(w);
E[++m]=(edge){u,v,w};
f[u]=min(f[u],w+1);
f[v]=min(f[v],w+2);
}
REP(i,0,2*n-1){
int pre= !(i%n) ? n-1 : i%n-1;
f[i%n]=min(f[i%n],f[pre]+2);
}
REP(i,0,n-1){
int nex=(i+1)%n;
E[++m]=(edge){i,nex,f[i]};
}
Kruskal::work();
return 0;
}
Submission Info
Submission Time |
|
Task |
G - Zigzag MST |
User |
ylsoi |
Language |
C++14 (GCC 5.4.1) |
Score |
1300 |
Code Size |
1524 Byte |
Status |
AC |
Exec Time |
79 ms |
Memory |
13056 KB |
Compile Error
./Main.cpp: In function ‘void File()’:
./Main.cpp:15:29: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen("gkk.in","r",stdin);
^
./Main.cpp:16:31: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
freopen("gkk.out","w",stdout);
^
Judge Result
Set Name |
sample |
all |
Score / Max Score |
0 / 0 |
1300 / 1300 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt, sample-03.txt |
all |
sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
2 ms |
1792 KB |
01-02.txt |
AC |
42 ms |
5120 KB |
01-03.txt |
AC |
77 ms |
10240 KB |
01-04.txt |
AC |
22 ms |
8192 KB |
01-05.txt |
AC |
14 ms |
6912 KB |
01-06.txt |
AC |
18 ms |
7424 KB |
01-07.txt |
AC |
17 ms |
6272 KB |
01-08.txt |
AC |
17 ms |
6016 KB |
01-09.txt |
AC |
21 ms |
5888 KB |
01-10.txt |
AC |
48 ms |
7936 KB |
01-11.txt |
AC |
65 ms |
7552 KB |
01-12.txt |
AC |
78 ms |
9984 KB |
01-13.txt |
AC |
77 ms |
9984 KB |
01-14.txt |
AC |
78 ms |
9984 KB |
01-15.txt |
AC |
79 ms |
9984 KB |
01-16.txt |
AC |
77 ms |
9984 KB |
01-17.txt |
AC |
77 ms |
9984 KB |
01-18.txt |
AC |
57 ms |
13056 KB |
01-19.txt |
AC |
17 ms |
6272 KB |
01-20.txt |
AC |
21 ms |
5888 KB |
01-21.txt |
AC |
36 ms |
7936 KB |
01-22.txt |
AC |
61 ms |
9984 KB |
01-23.txt |
AC |
61 ms |
9984 KB |
01-24.txt |
AC |
17 ms |
11008 KB |
01-25.txt |
AC |
77 ms |
13056 KB |
01-26.txt |
AC |
22 ms |
8576 KB |
01-27.txt |
AC |
23 ms |
7424 KB |
01-28.txt |
AC |
52 ms |
9472 KB |
01-29.txt |
AC |
61 ms |
8448 KB |
01-30.txt |
AC |
72 ms |
11520 KB |
sample-01.txt |
AC |
2 ms |
1792 KB |
sample-02.txt |
AC |
2 ms |
1792 KB |
sample-03.txt |
AC |
2 ms |
1792 KB |