Submission #7940011


Source Code Expand

#include<bits/stdc++.h>
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[2001000];
int head[2001000],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[2001000];
int fa[555000],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+1,edge+1+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_bot1
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1477 Byte
Status WA
Exec Time 102 ms
Memory 15488 KB

Judge Result

Set Name sample all
Score / Max Score 0 / 0 0 / 1300
Status
AC × 1
WA × 2
AC × 3
WA × 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, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 4 ms 10496 KB
01-02.txt WA 45 ms 12544 KB
01-03.txt WA 97 ms 15360 KB
01-04.txt WA 14 ms 13312 KB
01-05.txt WA 14 ms 13312 KB
01-06.txt WA 14 ms 13312 KB
01-07.txt WA 14 ms 13312 KB
01-08.txt WA 15 ms 13312 KB
01-09.txt WA 22 ms 13312 KB
01-10.txt WA 64 ms 15360 KB
01-11.txt WA 75 ms 14976 KB
01-12.txt WA 95 ms 15360 KB
01-13.txt WA 96 ms 15360 KB
01-14.txt WA 96 ms 15360 KB
01-15.txt WA 97 ms 15360 KB
01-16.txt WA 96 ms 15360 KB
01-17.txt WA 96 ms 15360 KB
01-18.txt WA 60 ms 15360 KB
01-19.txt WA 14 ms 13312 KB
01-20.txt WA 15 ms 13312 KB
01-21.txt WA 32 ms 15360 KB
01-22.txt WA 60 ms 15360 KB
01-23.txt WA 60 ms 15360 KB
01-24.txt WA 19 ms 13312 KB
01-25.txt WA 102 ms 15488 KB
01-26.txt WA 14 ms 13312 KB
01-27.txt WA 19 ms 13312 KB
01-28.txt WA 49 ms 15360 KB
01-29.txt WA 58 ms 14976 KB
01-30.txt WA 68 ms 15360 KB
sample-01.txt WA 4 ms 10496 KB
sample-02.txt WA 4 ms 10496 KB
sample-03.txt AC 4 ms 10496 KB