Submission #11134

#	Time	Username	Problem	Language	Result	Execution time	Memory
11134		dohyun0324	전압 (JOI14_voltage)	C++98	10 / 100	120 ms	20140 KiB

voltage

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stdlib.h>
using namespace std;
vector<int>con[100010];
int sw[100010],dap,n,m,x,y,ch[100010],anc[100010],arr[100010],w,top,lev[100010],check[100010],check2[100010];
struct data{
    int x,y,z;
    bool operator<(const data&r)const
    {
        return z<r.z;
    }
}a[400010];
void dfs(int prev,int x,int p)
{
    int i;
    ch[x]=1; arr[++w]=x; lev[x]=p;
    for(i=0;i<con[x].size();i++){
        if(con[x][i]==prev && sw[x]==0){sw[x]=1; continue;}
        if(ch[con[x][i]]){
            if(lev[x]>=lev[con[x][i]]){top++; a[top].x=x; a[top].y=con[x][i];}
            continue;
        }
        anc[con[x][i]]=x;
        dfs(x,con[x][i],p+1);
    }
}
void pro()
{
    int i,s,p,sw=0,t=0,r,r2,cnt=0,cnt1=0,cnt2=0;
    for(i=1;i<=top;i++) a[i].z=lev[a[i].y];
    sort(a+1,a+top+1);
    for(i=1;i<=top;i++){
        s=lev[a[i].x]-lev[a[i].y];
        if(s%2==1){
            p=a[i].x; cnt1++;
            while(check[p]==0){
                if(p==a[i].y) break;
                check[p]=1; cnt2++;
                p=anc[p];
            }
        }
        else if(!sw){
            sw=1;
            p=a[i].x; r=p; r2=a[i].y;
            while(1){
                if(p==a[i].y) break;
                check2[p]=1;
                p=anc[p];
            }
        }
    }
    if(sw==0)
    {
        dap+=w-1-cnt2;
        return;
    }
    for(i=1;i<=top;i++)
    {
        s=lev[a[i].x]-lev[a[i].y];
        if(s%2==0)
        {
            p=a[i].x;
            while(check2[p]==0){
                if(p==a[i].y || check2[p]==2 || check2[p]==3) break;
                if(check2[p]==1){check2[p]=3; break;}
                check2[p]=2;
                p=anc[p];
            }
        }
    }
    cnt=0; p=0;
    while(1)
    {
        if(r==r2) break;
        if(check2[r]==3) p=cnt;
        if(check[r]==0) cnt++;
        r=anc[r];
    }
    if(dap && (cnt-p)){printf("0"); exit(0);}
    if(dap && (top-cnt1)){printf("0"); exit(0);}
    dap+=(cnt-p);
    if(top-cnt1==1) dap++;
}
int main()
{
    int i;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++){scanf("%d %d",&x,&y); con[x].push_back(y); con[y].push_back(x);}
    for(i=1;i<=n;i++){
        if(ch[i]==0)
        {
            dfs(0,i,1);
            pro(); top=0; w=0;
        }
    }
    printf("%d",dap);
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 35
• Subtask 4: 0 / 45