Submission #2125988
Source Code Expand
#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; 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 Solve(int x) { int res=Abs(x); for(int s=A;s!=C;s=Fa[s]) g[s][0]+=x; for(int s=B;s!=C;s=Fa[s]) g[s][1]+=x; for(int i=1;i<=n;++i) res+=Abs(g[i][0]-g[i][1]); for(int s=A;s!=C;s=Fa[s]) g[s][0]-=x; for(int s=B;s!=C;s=Fa[s]) g[s][1]-=x; return mn=min(mn,res),res; } 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; dfs(1); if(num&1) printf("%d\n",ans+Abs(g[1][0]-g[1][1])/2); else { if(g[1][0]!=g[1][1]) return 0*puts("-1"); int l=-n,r=n; while(r-l+1>2) { int m1=l+(r-l+1)/3,m2=m1+(r-l+1)/3; int res1=Solve(m1),res2=Solve(m2); if(res1<res2) r=m2-1; else l=m1+1; } while(l<=r) Solve(l++); printf("%d\n",mn); } } return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Namori |
User | FallDream |
Language | C++14 (GCC 5.4.1) |
Score | 1500 |
Code Size | 2588 Byte |
Status | WA |
Exec Time | 169 ms |
Memory | 9216 KB |
Judge Result
Set Name | Sample | Subtask1 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1500 / 1500 | 0 / 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 | 1 ms | 2304 KB |
1_00.txt | AC | 2 ms | 2304 KB |
1_01.txt | AC | 18 ms | 8576 KB |
1_02.txt | AC | 15 ms | 5376 KB |
1_03.txt | AC | 12 ms | 4096 KB |
1_04.txt | AC | 16 ms | 6144 KB |
1_05.txt | AC | 17 ms | 6016 KB |
1_06.txt | AC | 17 ms | 6016 KB |
1_07.txt | AC | 16 ms | 5376 KB |
1_08.txt | AC | 17 ms | 6272 KB |
1_09.txt | AC | 14 ms | 4096 KB |
1_10.txt | AC | 14 ms | 4096 KB |
1_11.txt | AC | 15 ms | 4096 KB |
1_12.txt | AC | 15 ms | 4096 KB |
1_13.txt | AC | 1 ms | 256 KB |
1_14.txt | AC | 15 ms | 4096 KB |
1_15.txt | AC | 15 ms | 4096 KB |
1_16.txt | AC | 1 ms | 256 KB |
1_17.txt | AC | 15 ms | 4096 KB |
2_00.txt | AC | 2 ms | 2304 KB |
2_01.txt | WA | 169 ms | 9216 KB |
2_02.txt | WA | 95 ms | 6656 KB |
2_03.txt | AC | 20 ms | 4096 KB |
2_04.txt | WA | 96 ms | 6656 KB |
2_05.txt | WA | 95 ms | 6656 KB |
2_06.txt | WA | 97 ms | 6656 KB |
2_07.txt | WA | 95 ms | 6656 KB |
2_08.txt | WA | 95 ms | 6656 KB |
2_09.txt | AC | 21 ms | 4096 KB |
2_10.txt | AC | 23 ms | 4096 KB |
2_11.txt | AC | 23 ms | 4096 KB |
2_12.txt | AC | 24 ms | 4224 KB |
2_13.txt | AC | 1 ms | 256 KB |
2_14.txt | AC | 18 ms | 4352 KB |
2_15.txt | AC | 24 ms | 4224 KB |
2_16.txt | AC | 1 ms | 256 KB |
2_17.txt | AC | 24 ms | 4224 KB |
2_18.txt | AC | 1 ms | 256 KB |
2_19.txt | WA | 19 ms | 6656 KB |
2_20.txt | WA | 14 ms | 4096 KB |
2_21.txt | WA | 169 ms | 9216 KB |
2_22.txt | WA | 21 ms | 6656 KB |
2_23.txt | WA | 21 ms | 6656 KB |
2_24.txt | WA | 22 ms | 6656 KB |
2_25.txt | WA | 21 ms | 6656 KB |
2_26.txt | WA | 22 ms | 6656 KB |
2_27.txt | WA | 16 ms | 4096 KB |
2_28.txt | WA | 17 ms | 4224 KB |
2_29.txt | WA | 17 ms | 4224 KB |
2_30.txt | AC | 18 ms | 4224 KB |
2_31.txt | AC | 1 ms | 256 KB |
2_32.txt | WA | 19 ms | 4352 KB |
2_33.txt | WA | 19 ms | 4224 KB |
2_34.txt | AC | 1 ms | 256 KB |
2_35.txt | AC | 19 ms | 4224 KB |
2_36.txt | AC | 19 ms | 4096 KB |
2_37.txt | AC | 19 ms | 4096 KB |
2_38.txt | AC | 19 ms | 4096 KB |
2_39.txt | AC | 20 ms | 4096 KB |
2_40.txt | AC | 19 ms | 4096 KB |
2_41.txt | AC | 19 ms | 4096 KB |
2_42.txt | AC | 20 ms | 4096 KB |
2_43.txt | AC | 19 ms | 4096 KB |