Submission #3414941
Source Code Expand
#include<bits/stdc++.h> using namespace std; namespace IO { char ibuf[(1<<21)+1],obuf[(1<<21)+1],st[15],*iS,*iT,*oS=obuf,*oT=obuf+(1<<21); inline char Get() { return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++); } inline void Flush() { fwrite(obuf,1,oS-obuf,stdout); oS=obuf; } inline void Put(char x) { *oS++=x; if(oS==oT) Flush(); } inline int read() { register int x=0; register char ch=Get(); while(ch>'9'||ch<'0') ch=Get(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=Get(); return x; } inline void write(int x) { register int top=0; while(x) st[++top]=(x%10)+48,x/=10; while(top) Put(st[top--]); } } using namespace IO; const int N=200001,M=N<<3; struct Edge { int u,v,w,Next; Edge(){} Edge(int U,int V,int W,int NEXT) { u=U,v=V,w=W,Next=NEXT; } bool operator<(Edge a)const { return w<a.w; } }edge[M]; int head[N],tot,f[N],d[N]; inline void add(int x,int y,int z) { edge[++tot]=Edge(x,y,z,head[x]),head[x]=tot; } int find(int x) { return x==f[x]? x:f[x]=find(f[x]); } bool cmp(int x,int y) { int fx=find(x),fy=find(y); if(fx==fy) return false; if(fy>fx) f[fy]=fx; else f[fx]=fy; return true; } int main() { register int n=read(),q=read(); memset(d,0x3f sizeof d); for(register int i=1,a,b,c;i<=q;++i) { a=read(),b=read(),c=read(); add(a,b,c); d[a]=min(d[a],c+1),d[b]=min(d[b],c+2); } for(register int i=0;i<n;++i) d[i]=min(d[i],d[(i-1+n)%n]+2); for(register int i=0;i<n;++i) d[i]=min(d[i],d[(i-1+n)%n]+2); for(register int i=0;i<=n;++i) add(i,(i+1)%n,d[i]); sort(edge+1,edge+1+tot); for(register int i=1;i<n;++i) f[i]=i; register int lt=n,ans=0; for(register int i=1;i<=tot&<>1;++i) if(cmp(edge[i].u, edge[i].v)) ans+=edge[i].w,--lt; return printf("%lld", ans),0; }
Submission Info
Submission Time | |
---|---|
Task | G - Zigzag MST |
User | luogu_bot5 |
Language | C++ (GCC 5.4.1) |
Score | 0 |
Code Size | 2088 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:78:19: error: expected ‘)’ before ‘sizeof’ memset(d,0x3f sizeof d); ^ ./Main.cpp:78:27: error: too few arguments to function ‘void* memset(void*, int, size_t)’ memset(d,0x3f sizeof d); ^ In file included from /usr/include/features.h:374:0, from /usr/include/assert.h:35, from /usr/include/c++/5/cassert:43, from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:33, from ./Main.cpp:1: /usr/include/x86_64-linux-gnu/bits/string3.h:76:1: note: declared here __NTH (memset (void *__dest, int __ch, size_t __len)) ^ ./Main.cpp:98:30: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int’ [-Wformat=] return printf("%lld", ans),0; ^