Submission #4413236


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
long long n,m,cnt = 0;
long long dis[200010];
struct edge {
	long long u,v,len;
}e[500010];
long long fa[200010];
bool cmp(edge x,edge y){
	return x.len<y.len;
}
long long get(long long x){
	if (fa[x]==x){
		return x;
	}
	return fa[x]=get(fa[x]);
}
int main () {
	scanf("%lld%lld",&n,&m);
	for (register int i = 0; i <= n; i++){
		fa[i] = i;
		dis[i] = 1e18;
	}
	for (register int i = 1; i <= m; i++){
		long long a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		e[++cnt].u = a;
		e[cnt].v = b;
		e[cnt].len = c;
		dis[a] = min(dis[a],c+1);
		dis[b] = min(dis[b],c+2);
	}
	for (register int i = 0; i <= n; i++){
		dis[i] = min(dis[i],dis[(i-1+n)%n]+2);
	}
	for (register int i = 0; i <= n; i++){
		dis[i] = min(dis[i],dis[(i-1+n)%n]+2);
	}
	for (register int i = 0; i < n; i++){
		e[++cnt].u = i;
		e[cnt].v = (i+1)%n;
		e[cnt].len = dis[i];
	}
	sort(e+1,e+cnt+1,cmp);
	long long ans = 0,ccnt = 0;
	for (register int i = 1; i <= cnt; i++){
		int fx = get(e[i].u);
		int fy = get(e[i].v);
		//cout << fx << " " << fy << " " << e[i].len << endl;
		if (fx!=fy){
			fa[fx] = fy;
			ans += e[i].len;
			ccnt++;
		}
		if (ccnt==n-1){
			break;
		}
	}
	printf("%lld",ans);
	return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User luogu_bot1
Language C++ (GCC 5.4.1)
Score 1300
Code Size 1278 Byte
Status AC
Exec Time 144 ms
Memory 15360 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:19:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&m);
                         ^
./Main.cpp:26:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&a,&b,&c);
                                 ^

Judge Result

Set Name sample all
Score / Max Score 0 / 0 1300 / 1300
Status
AC × 3
AC × 36
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 2304 KB
01-02.txt AC 73 ms 8960 KB
01-03.txt AC 119 ms 15360 KB
01-04.txt AC 48 ms 13312 KB
01-05.txt AC 33 ms 12032 KB
01-06.txt AC 41 ms 12544 KB
01-07.txt AC 34 ms 11392 KB
01-08.txt AC 33 ms 11136 KB
01-09.txt AC 37 ms 11008 KB
01-10.txt AC 74 ms 13056 KB
01-11.txt AC 99 ms 11776 KB
01-12.txt AC 117 ms 15104 KB
01-13.txt AC 117 ms 15104 KB
01-14.txt AC 117 ms 15104 KB
01-15.txt AC 120 ms 15104 KB
01-16.txt AC 117 ms 15104 KB
01-17.txt AC 117 ms 15104 KB
01-18.txt AC 98 ms 15104 KB
01-19.txt AC 34 ms 11392 KB
01-20.txt AC 35 ms 11008 KB
01-21.txt AC 57 ms 11008 KB
01-22.txt AC 104 ms 15104 KB
01-23.txt AC 104 ms 15104 KB
01-24.txt AC 33 ms 11008 KB
01-25.txt AC 144 ms 15104 KB
01-26.txt AC 47 ms 11008 KB
01-27.txt AC 42 ms 11008 KB
01-28.txt AC 83 ms 13056 KB
01-29.txt AC 98 ms 11904 KB
01-30.txt AC 117 ms 15104 KB
sample-01.txt AC 2 ms 2304 KB
sample-02.txt AC 1 ms 2304 KB
sample-03.txt AC 1 ms 2304 KB