oj.uz

Submission #11133

# Submission time Handle Problem Language Result Execution time Memory
11133 2014-11-14T17:51:52 Z dohyun0324 전압 (JOI14_voltage) C++
10 / 100
 112 ms 18576 KB 
#include<stdio.h>
#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;
}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++){
        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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9412 KB Output is correct
2 Correct 0 ms 9412 KB Output is correct
3 Correct 0 ms 9412 KB Output is correct
4 Correct 0 ms 9412 KB Output is correct
5 Incorrect 0 ms 9412 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 12964 KB Output is correct
2 Correct 80 ms 15932 KB Output is correct
3 Correct 60 ms 12964 KB Output is correct
4 Correct 96 ms 17228 KB Output is correct
5 Correct 8 ms 9756 KB Output is correct
6 Correct 88 ms 14476 KB Output is correct
7 Correct 108 ms 18572 KB Output is correct
8 Correct 88 ms 18576 KB Output is correct

Subtask #3
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12964 KB Output is correct
2 Correct 52 ms 18572 KB Output is correct
3 Correct 60 ms 18576 KB Output is correct
4 Correct 0 ms 9412 KB Output is correct
5 Incorrect 72 ms 14768 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 13988 KB Output is correct
2 Correct 76 ms 18568 KB Output is correct
3 Correct 4 ms 9412 KB Output is correct
4 Incorrect 112 ms 15912 KB Output isn't correct
5 Halted 0 ms 0 KB -