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
AC × 3
AC × 33
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