Submission #11158

#	Time	Username	Problem	Language	Result	Execution time	Memory
11158		dohyun0324	전압 (JOI14_voltage)	C++98	100 / 100	252 ms	29124 KiB

voltage

#pragma pack(1)
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#define M 100010
using namespace std;
vector<int>con[M];
int arr3[M],dp[M][21],arr2[M],dap2,sw[M],dap,n,m,x,y,ch[M],anc[M],arr[M],w,top,lev[M],check[M],check2[M];
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);
    }
}
int LCA(int x,int y)
{
    int i;
    if(lev[x]<lev[y]) swap(x,y);
    for(i=0;i<=20;i++){
        if((lev[x]-lev[y])&(1<<i)){
            x=dp[x][i];
        }
    }
    if(x==y){return x; return 0;}
    for(i=20;i>=0;i--){
        if(dp[x][i]!=0 && dp[x][i]!=dp[y][i]){x=dp[x][i]; y=dp[y][i];}
    }
    return dp[x][0];
}
void pro()
{
    int i,j,s,p,sw=0,r,r2,cnt=0,cnt1=0,cnt2=0,gap=0,t=0,w2=0;
    for(i=1;i<=w;i++) dp[arr[i]][0]=anc[arr[i]];
    for(j=1;j<=20;j++){
        for(i=1;i<=w;i++){
            dp[arr[i]][j]=dp[dp[arr[i]][j-1]][j-1];
        }
    }
    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; t=s;
            while(1){
                if(p==a[i].y) break;
                check2[p]=++w2; arr3[w2]=p;
                p=anc[p];
            }
        }
    }
    if(sw==0){dap2+=w-1-cnt2; return;}
    sw=0;
    for(i=1;i<=top;i++){
        s=lev[a[i].x]-lev[a[i].y];
        if(s%2==0){
            sw++; if(sw==1) continue;
            p=LCA(r,a[i].x);
            if(check2[p]==0 || lev[p]<lev[a[i].y]){printf("0"); exit(0);}
            arr2[check2[p]]++; arr2[check2[a[i].y]]--;
        }
    }
    p=0; cnt=0;
    for(i=1;i<=w2;i++){
        p+=arr2[i]; arr2[i]=0;
        if(check[arr3[i]]==0 && p==sw-1) cnt++;
    }
    if(cnt==0 && top-cnt1>=2){printf("0"); exit(0);}
    if(dap && cnt){printf("0"); exit(0);}
    if(dap && (top-cnt1)){printf("0"); exit(0);}
    dap+=cnt;
    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;
        }
    }
    if(dap==0) printf("%d",dap2);
    else printf("%d",dap);
    return 0;
}

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