Submission #7939961


Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define il inline
const int inf=2147483647;
il int read()
{
int x=0;int f=1;
char s=getchar();
while(s<'0' || s>'9')
{if(s=='-')f=-1;s=getchar();}
while(s>='0' && s<='9')
{x=x*10+s-'0';s=getchar();
}
return x*f;		
}

struct Edge
{int u,v,w;}edge[200100];
int head[200100],tot;
//void add(int x,int y,int w){
  //  ed[++tot].nxt=head[x];
	//ed[tot].to=y;
	///./ed[tot].w=w;
	//head[x]
int Min_value[200100];
int fa[5550],n,q,ans,eu,ev,cnt;

il bool cmp(Edge a,Edge b)
{return a.w<b.w;}

il int Union(int x)
{while(x!=fa[x])x=fa[x]=fa[fa[x]];
return x;}

il void kruscal()
{
sort (edge,edge+cnt,cmp);
for(int i=1;i<=cnt;i++)
{int ttt=0;
int eu=Union(edge[i].u);
int ev=Union(edge[i].v);
if(eu==ev){continue;}
	ans+=edge[i].w;
	fa[eu]=ev;++ttt; 
	if(ttt==n-1)
	{break;}}}
int main()
{
	n=read();
	q=read();
    memset(Min_value,0x3f,sizeof(Min_value));
    while(q--)
    {
        int u=read()+1;int v=read()+1;int w=read();
        edge[++cnt]=(Edge){u,v,w};
        Min_value[u]=min(Min_value[u],w+1);
        Min_value[v]=min(Min_value[v],w+2);
    }
	for(int i=1;i<=n;i++)
	{fa[i]=i;}
	for(int i=1;i<=n;i++){
		Min_value[i]=min(Min_value[i%n+1],Min_value[i]+2);
	}
	for(int i=1;i<=n;i++){
		Min_value[i]=min(Min_value[i%n+1],Min_value[i]+2);
	}
	for(int i=1;i<=n;i++){
		edge[++cnt]=(Edge){i,i%n+1,Min_value[i]};
	}
kruscal();
cout<<ans;
return 0;
}

Submission Info

Submission Time
Task G - Zigzag MST
User luogu_bot2
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1540 Byte
Status RE
Exec Time 139 ms
Memory 3328 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 0 / 1300
Status
AC × 2
WA × 1
AC × 5
WA × 3
RE × 28
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 1024 KB
01-02.txt WA 43 ms 3328 KB
01-03.txt RE 136 ms 3328 KB
01-04.txt RE 111 ms 3328 KB
01-05.txt RE 109 ms 3328 KB
01-06.txt RE 133 ms 3328 KB
01-07.txt RE 131 ms 3328 KB
01-08.txt RE 106 ms 3328 KB
01-09.txt RE 105 ms 3328 KB
01-10.txt RE 120 ms 3328 KB
01-11.txt RE 135 ms 3328 KB
01-12.txt RE 137 ms 3328 KB
01-13.txt RE 136 ms 3328 KB
01-14.txt RE 137 ms 3328 KB
01-15.txt RE 137 ms 3328 KB
01-16.txt RE 136 ms 3328 KB
01-17.txt RE 136 ms 3328 KB
01-18.txt RE 134 ms 3328 KB
01-19.txt RE 137 ms 3328 KB
01-20.txt RE 106 ms 3328 KB
01-21.txt RE 110 ms 3328 KB
01-22.txt RE 125 ms 3328 KB
01-23.txt RE 128 ms 3328 KB
01-24.txt RE 102 ms 3328 KB
01-25.txt RE 139 ms 3328 KB
01-26.txt RE 112 ms 3328 KB
01-27.txt RE 104 ms 3328 KB
01-28.txt RE 124 ms 3328 KB
01-29.txt RE 135 ms 3328 KB
01-30.txt RE 139 ms 3328 KB
sample-01.txt AC 2 ms 1024 KB
sample-02.txt WA 2 ms 1024 KB
sample-03.txt AC 2 ms 1024 KB