Submission #2126062
Source Code Expand
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #define MN 100000 using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*f; } int n,m,head[MN+5],cnt=1,ans=0,f[MN+5],g[MN+5][2],Fa[MN+5],dep[MN+5],A,B,C,c[MN+5],num,mn=1e9,q[MN+5],top; struct edge{int to,next;}e[MN*2+5]; inline void ins(int f,int t) { e[++cnt]=(edge){t,head[f]};head[f]=cnt; e[++cnt]=(edge){f,head[t]};head[t]=cnt; } inline int Abs(int x){return x<0?-x:x;} void dfs(int x,int fa=0) { ++g[x][f[x]]; for(int i=head[x];i;i=e[i].next) if(e[i].to!=fa) { if(x==A&&e[i].to==B) continue; if(x==B&&e[i].to==A) continue; f[e[i].to]=f[x]^1;dfs(e[i].to,x); g[x][0]+=g[e[i].to][0]; g[x][1]+=g[e[i].to][1]; } ans+=Abs(g[x][0]-g[x][1]); } void FindCircle(int x,int fa) { Fa[x]=fa; for(int i=head[x];i;i=e[i].next) if(e[i].to!=fa) { if(dep[e[i].to]) A=x,B=e[i].to; else dep[e[i].to]=dep[x]+1,FindCircle(e[i].to,x); } } int main() { n=read();m=read();if(n&1) return 0*puts("-1"); if(m<n) { for(int i=1;i<n;++i) ins(read(),read()); dfs(1); printf("%d\n",g[1][0]==g[1][1]?ans:-1); } else { for(int i=1;i<=n;++i) ins(read(),read()); FindCircle(dep[1]=1,0); for(int x=A,y=B;x!=y;C=x=Fa[x]) if(dep[x]<dep[y]) swap(x,y); for(int i=A;i!=C;i=Fa[i]) c[++num]=i; c[++num]=C;int len=dep[A]+dep[B]-2*dep[C]+1;num=len; for(int i=B;i!=C;i=Fa[i]) c[len--]=i; if(dfs(1),num&1) { if(Abs(g[1][1]-g[1][0])&1) return 0*puts("-1"); int dif=(g[1][1]-g[1][0])/2;ans=Abs(dif); for(int i=A;i;i=Fa[i]) g[i][0]+=dif; for(int i=B;i;i=Fa[i]) g[i][0]+=dif; for(int i=1;i<=n;++i) ans+=Abs(g[i][0]-g[i][1]); printf("%d\n",ans); } else { if(g[1][0]!=g[1][1]) return 0*puts("-1"); for(int i=A;i!=C;i=Fa[i]) q[++top]=g[i][0]-g[i][1]; for(int i=B;i!=C;i=Fa[i]) q[++top]=g[i][1]-g[i][0]; sort(q+1,q+top+1); int res; if(top&1) res=q[(top+1)/2]; else res=Abs(q[top/2])<Abs(q[top/2+1])?q[top/2]:q[top/2+1]; res=-res; for(int i=A;i;i=Fa[i]) g[i][0]+=res; for(int i=B;i;i=Fa[i]) g[i][1]+=res; ans=Abs(res);for(int i=1;i<=n;++i) ans+=Abs(g[i][0]-g[i][1]); printf("%d\n",ans); } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Namori |
User | FallDream |
Language | C++14 (GCC 5.4.1) |
Score | 2200 |
Code Size | 2799 Byte |
Status | AC |
Exec Time | 29 ms |
Memory | 9600 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1500 / 1500 | 700 / 700 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
Subtask1 | 0_00.txt, 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 2_00.txt, 2_01.txt, 2_02.txt, 2_03.txt, 2_04.txt, 2_05.txt, 2_06.txt, 2_07.txt, 2_08.txt, 2_09.txt, 2_10.txt, 2_11.txt, 2_12.txt, 2_13.txt, 2_14.txt, 2_15.txt, 2_16.txt, 2_17.txt, 2_18.txt, 2_19.txt, 2_20.txt, 2_21.txt, 2_22.txt, 2_23.txt, 2_24.txt, 2_25.txt, 2_26.txt, 2_27.txt, 2_28.txt, 2_29.txt, 2_30.txt, 2_31.txt, 2_32.txt, 2_33.txt, 2_34.txt, 2_35.txt, 2_36.txt, 2_37.txt, 2_38.txt, 2_39.txt, 2_40.txt, 2_41.txt, 2_42.txt, 2_43.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 2 ms | 2304 KB |
0_01.txt | AC | 1 ms | 256 KB |
0_02.txt | AC | 1 ms | 2304 KB |
0_03.txt | AC | 2 ms | 2304 KB |
1_00.txt | AC | 2 ms | 2304 KB |
1_01.txt | AC | 20 ms | 8960 KB |
1_02.txt | AC | 17 ms | 5760 KB |
1_03.txt | AC | 14 ms | 4480 KB |
1_04.txt | AC | 18 ms | 6528 KB |
1_05.txt | AC | 19 ms | 6400 KB |
1_06.txt | AC | 19 ms | 6400 KB |
1_07.txt | AC | 18 ms | 5760 KB |
1_08.txt | AC | 18 ms | 6784 KB |
1_09.txt | AC | 15 ms | 4480 KB |
1_10.txt | AC | 16 ms | 4480 KB |
1_11.txt | AC | 16 ms | 4480 KB |
1_12.txt | AC | 17 ms | 4480 KB |
1_13.txt | AC | 1 ms | 256 KB |
1_14.txt | AC | 17 ms | 4480 KB |
1_15.txt | AC | 16 ms | 4480 KB |
1_16.txt | AC | 1 ms | 256 KB |
1_17.txt | AC | 17 ms | 4480 KB |
2_00.txt | AC | 1 ms | 2304 KB |
2_01.txt | AC | 29 ms | 9600 KB |
2_02.txt | AC | 22 ms | 7040 KB |
2_03.txt | AC | 14 ms | 4480 KB |
2_04.txt | AC | 25 ms | 7040 KB |
2_05.txt | AC | 26 ms | 7040 KB |
2_06.txt | AC | 25 ms | 7040 KB |
2_07.txt | AC | 24 ms | 7040 KB |
2_08.txt | AC | 25 ms | 7040 KB |
2_09.txt | AC | 17 ms | 4480 KB |
2_10.txt | AC | 18 ms | 4480 KB |
2_11.txt | AC | 18 ms | 4480 KB |
2_12.txt | AC | 19 ms | 4480 KB |
2_13.txt | AC | 1 ms | 256 KB |
2_14.txt | AC | 19 ms | 4736 KB |
2_15.txt | AC | 19 ms | 4480 KB |
2_16.txt | AC | 1 ms | 256 KB |
2_17.txt | AC | 19 ms | 4480 KB |
2_18.txt | AC | 1 ms | 256 KB |
2_19.txt | AC | 21 ms | 6912 KB |
2_20.txt | AC | 14 ms | 4480 KB |
2_21.txt | AC | 29 ms | 9600 KB |
2_22.txt | AC | 22 ms | 6912 KB |
2_23.txt | AC | 22 ms | 6912 KB |
2_24.txt | AC | 23 ms | 6912 KB |
2_25.txt | AC | 22 ms | 6912 KB |
2_26.txt | AC | 23 ms | 6912 KB |
2_27.txt | AC | 17 ms | 4480 KB |
2_28.txt | AC | 18 ms | 4480 KB |
2_29.txt | AC | 18 ms | 4480 KB |
2_30.txt | AC | 19 ms | 4480 KB |
2_31.txt | AC | 1 ms | 256 KB |
2_32.txt | AC | 19 ms | 4608 KB |
2_33.txt | AC | 19 ms | 4480 KB |
2_34.txt | AC | 1 ms | 256 KB |
2_35.txt | AC | 19 ms | 4480 KB |
2_36.txt | AC | 14 ms | 4480 KB |
2_37.txt | AC | 14 ms | 4480 KB |
2_38.txt | AC | 14 ms | 4480 KB |
2_39.txt | AC | 14 ms | 4480 KB |
2_40.txt | AC | 14 ms | 4480 KB |
2_41.txt | AC | 15 ms | 4480 KB |
2_42.txt | AC | 14 ms | 4480 KB |
2_43.txt | AC | 14 ms | 4480 KB |