Submission #2126061

---

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,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

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:77:29: error: ‘sort’ was not declared in this scope
             sort(q+1,q+top+1);
                             ^