oj.uz

Submission #11134

# Submission time Handle Problem Language Result Execution time Memory
11134 2014-11-14T18:04:44 Z dohyun0324 전압 (JOI14_voltage) C++
10 / 100
 120 ms 20140 KB 
#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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 14528 KB Output is correct
2 Correct 100 ms 17492 KB Output is correct
3 Correct 80 ms 14528 KB Output is correct
4 Correct 92 ms 18792 KB Output is correct
5 Correct 4 ms 11328 KB Output is correct
6 Correct 76 ms 16044 KB Output is correct
7 Correct 108 ms 20136 KB Output is correct
8 Correct 100 ms 20136 KB Output is correct

Subtask #3
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 14528 KB Output is correct
2 Correct 40 ms 20132 KB Output is correct
3 Correct 36 ms 20140 KB Output is correct
4 Correct 0 ms 10976 KB Output is correct
5 Incorrect 76 ms 16332 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 60 ms 15552 KB Output is correct
2 Correct 104 ms 20136 KB Output is correct
3 Correct 0 ms 10976 KB Output is correct
4 Correct 120 ms 17476 KB Output is correct
5 Correct 104 ms 18500 KB Output is correct
6 Incorrect 92 ms 17188 KB Output isn't correct
7 Halted 0 ms 0 KB -