Submission #6360267


Source Code Expand

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
#define N 400002
using namespace std;
struct edge{
	int u,v,w;
}e[N];
int n,q,i,f[N],num,fa[N];
int read()
{
	char c=getchar();
	int w=0;
	while(c<'0'||c>'9') c=getchar();
	while(c<='9'&&c>='0'){
		w=w*10+c-'0';
		c=getchar();
	}
	return w;
}
int my_comp(const edge &x,const edge &y)
{
	return x.w<y.w;
}
int find(int x)
{
	if(x!=fa[x]) fa[x]=find(fa[x]);
	return fa[x];
}
int Kruscal()
{
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(e+1,e+num+1,my_comp);
	int cnt=n,ans=0;
	for(int i=1;i<=num;i++){
		int f1=find(e[i].u),f2=find(e[i].v);
		if(f1!=f2){
			fa[f1]=f2;
			cnt--;
			ans+=e[i].w;
		}
	}
	return ans;
}
signed main()
{
	memset(f,0x3f,sizeof(f));
	n=read();q=read();
	for(i=1;i<=q;i++){
		int a,b,c;
		a=read()+1;b=read()+1;c=read();
		e[++num]=(edge){a,b,c};
		f[a]=min(f[a],c+1);
		f[b]=min(f[b],c+2);
	}
	bool flag=0;
	for(i=1;i<=n;i++){
		f[i%n+1]=min(f[i]+2,f[i%n+1]);
		if(i==n&&!flag) i=0,flag=1;
	}
	for(i=1;i<=n;i++) e[++num]=(edge){i,i%n+1,f[i]};
	cout<<Kruscal()<<endl;
	return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User vjudge3
Language C++14 (GCC 5.4.1)
Score 1300
Code Size 1098 Byte
Status AC
Exec Time 111 ms
Memory 18560 KB

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 3 ms 6400 KB
01-02.txt AC 49 ms 10496 KB
01-03.txt AC 96 ms 15616 KB
01-04.txt AC 41 ms 14336 KB
01-05.txt AC 28 ms 13056 KB
01-06.txt AC 34 ms 13568 KB
01-07.txt AC 29 ms 12416 KB
01-08.txt AC 29 ms 12160 KB
01-09.txt AC 33 ms 12032 KB
01-10.txt AC 62 ms 14080 KB
01-11.txt AC 77 ms 13312 KB
01-12.txt AC 96 ms 15360 KB
01-13.txt AC 95 ms 15360 KB
01-14.txt AC 98 ms 15360 KB
01-15.txt AC 97 ms 15360 KB
01-16.txt AC 96 ms 15360 KB
01-17.txt AC 95 ms 15360 KB
01-18.txt AC 74 ms 18560 KB
01-19.txt AC 29 ms 12416 KB
01-20.txt AC 30 ms 12032 KB
01-21.txt AC 46 ms 14080 KB
01-22.txt AC 75 ms 15360 KB
01-23.txt AC 75 ms 15360 KB
01-24.txt AC 29 ms 15104 KB
01-25.txt AC 111 ms 18560 KB
01-26.txt AC 40 ms 14720 KB
01-27.txt AC 37 ms 13568 KB
01-28.txt AC 67 ms 15616 KB
01-29.txt AC 75 ms 14336 KB
01-30.txt AC 90 ms 16896 KB
sample-01.txt AC 3 ms 6400 KB
sample-02.txt AC 3 ms 6400 KB
sample-03.txt AC 3 ms 6400 KB