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
AC × 4
AC × 20
AC × 66
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