Submission #1049359
Source Code Expand
#include<cstdio> #include<algorithm> using namespace std; const int N=200200; int i,j,k,n,m,ch,num,v,a,b,c,Hn; long long ans; int f[N]; struct cc { int a,b,c,fg;} t,H[N]; void R(int &x) { x=0;ch=getchar(); while (ch<'0' || '9'<ch) ch=getchar(); while ('0'<=ch && ch<='9') x=x*10+ch-'0',ch=getchar(); } void W(long long x) { if (x>=10) W(x/10); putchar(x%10+'0'); } bool cmp(const cc &a,const cc &b) { return a.c<b.c; } void S(int x,int y) { t=H[x];H[x]=H[y];H[y]=t; } void up(int x) { while (x>1 && H[x].c<H[x>>1].c) S(x,x>>1),x>>=1; } void down(int x) { while ((x<<1)<=Hn) { int k=x<<1; if (k<Hn && H[k|1].c<H[k].c) k|=1; if (H[k].c<H[x].c) { S(k,x); x=k; } else break; } } int getf(int x) { if (f[x]==x) return x; return f[x]=getf(f[x]); } int main() { R(n);R(m); if (n<=500 && m<=500) { for (i=1;i<=n;i++) f[i]=i; for (i=1;i<=m;i++) { R(a);R(b);R(c); a++;b++;Hn=i; H[i].a=a;H[i].b=b;H[i].c=c; up(i); } num=1; while (num<n) { t=H[1]; if (getf(t.a)==getf(t.b)) { t.c++; k=t.b;t.b=t.a;t.a=k; if (++t.b>n) t.b-=n; H[1]=t; down(1); } else { f[f[t.a]]=f[t.b]; ans+=t.c; num++; t.c++; k=t.b;t.b=t.a;t.a=k; if (++t.b>n) t.b-=n; H[1]=t; down(1); } } W(ans);puts(""); return 0; } for (i=1;i<=n;i++) f[i]=i; for (i=1;i<=m;i++) { R(a);R(b);R(c); a++;b++;Hn=i; if (a==b) { H[i].fg=1; c++; k=b;b=a;a=k; if (++b>n) b-=n; } H[i].a=a;H[i].b=b;H[i].c=c; up(i); } num=1; while (num<n) { t=H[1]; if (getf(t.a)==getf(t.b)) { if (t.fg) { H[1]=H[Hn--]; down(1); continue; } t.fg=1; t.c++; k=t.b;t.b=t.a;t.a=k; if (++t.b>n) t.b-=n; H[1]=t; down(1); } else { f[f[t.a]]=f[t.b]; ans+=t.c; num++; if (t.fg) { t.c++; k=t.b;t.b=t.a;t.a=k; if (++t.b>n) t.b-=n; t.c++; k=t.b;t.b=t.a;t.a=k; if (++t.b>n) t.b-=n; } else { t.c++; k=t.b;t.b=t.a;t.a=k; if (++t.b>n) t.b-=n; } H[1]=t; down(1); } } W(ans);puts(""); }
Submission Info
Submission Time | |
---|---|
Task | G - Zigzag MST |
User | rxdoi |
Language | C++14 (GCC 5.4.1) |
Score | 1300 |
Code Size | 2173 Byte |
Status | AC |
Exec Time | 108 ms |
Memory | 4352 KB |
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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 1 ms | 128 KB |
01-02.txt | AC | 34 ms | 3328 KB |
01-03.txt | AC | 56 ms | 4352 KB |
01-04.txt | AC | 9 ms | 3200 KB |
01-05.txt | AC | 8 ms | 2048 KB |
01-06.txt | AC | 8 ms | 1664 KB |
01-07.txt | AC | 8 ms | 1152 KB |
01-08.txt | AC | 11 ms | 1152 KB |
01-09.txt | AC | 19 ms | 1152 KB |
01-10.txt | AC | 42 ms | 2560 KB |
01-11.txt | AC | 55 ms | 3712 KB |
01-12.txt | AC | 68 ms | 4096 KB |
01-13.txt | AC | 68 ms | 4096 KB |
01-14.txt | AC | 67 ms | 4096 KB |
01-15.txt | AC | 76 ms | 4096 KB |
01-16.txt | AC | 68 ms | 4096 KB |
01-17.txt | AC | 67 ms | 4096 KB |
01-18.txt | AC | 50 ms | 4096 KB |
01-19.txt | AC | 9 ms | 1280 KB |
01-20.txt | AC | 24 ms | 1024 KB |
01-21.txt | AC | 54 ms | 1792 KB |
01-22.txt | AC | 103 ms | 4096 KB |
01-23.txt | AC | 103 ms | 4096 KB |
01-24.txt | AC | 9 ms | 1152 KB |
01-25.txt | AC | 64 ms | 4096 KB |
01-26.txt | AC | 6 ms | 896 KB |
01-27.txt | AC | 26 ms | 1152 KB |
01-28.txt | AC | 78 ms | 2816 KB |
01-29.txt | AC | 92 ms | 3712 KB |
01-30.txt | AC | 108 ms | 4096 KB |
sample-01.txt | AC | 1 ms | 128 KB |
sample-02.txt | AC | 1 ms | 128 KB |
sample-03.txt | AC | 1 ms | 128 KB |