oj.uz

Submission #11158

# Submission time Handle Problem Language Result Execution time Memory
11158 2014-11-15T11:27:10 Z dohyun0324 전압 (JOI14_voltage) C++
100 / 100
 252 ms 29124 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 19960 KB Output is correct
2 Correct 0 ms 19960 KB Output is correct
3 Correct 0 ms 19960 KB Output is correct
4 Correct 0 ms 19960 KB Output is correct
5 Correct 4 ms 19960 KB Output is correct
6 Correct 0 ms 19960 KB Output is correct
7 Correct 0 ms 19960 KB Output is correct
8 Correct 0 ms 19960 KB Output is correct
9 Correct 0 ms 19960 KB Output is correct
10 Correct 0 ms 19960 KB Output is correct
11 Correct 0 ms 19960 KB Output is correct
12 Correct 0 ms 19960 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 23512 KB Output is correct
2 Correct 160 ms 26480 KB Output is correct
3 Correct 80 ms 23512 KB Output is correct
4 Correct 156 ms 27772 KB Output is correct
5 Correct 8 ms 20308 KB Output is correct
6 Correct 152 ms 25024 KB Output is correct
7 Correct 132 ms 29120 KB Output is correct
8 Correct 148 ms 29120 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 23512 KB Output is correct
2 Correct 60 ms 29124 KB Output is correct
3 Correct 52 ms 29120 KB Output is correct
4 Correct 0 ms 19960 KB Output is correct
5 Correct 100 ms 25320 KB Output is correct
6 Correct 132 ms 23128 KB Output is correct
7 Correct 136 ms 25692 KB Output is correct
8 Correct 152 ms 27060 KB Output is correct
9 Correct 144 ms 26768 KB Output is correct
10 Correct 152 ms 25424 KB Output is correct
11 Correct 132 ms 23128 KB Output is correct
12 Correct 140 ms 24476 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 24536 KB Output is correct
2 Correct 116 ms 29116 KB Output is correct
3 Correct 16 ms 19960 KB Output is correct
4 Correct 160 ms 26460 KB Output is correct
5 Correct 180 ms 27488 KB Output is correct
6 Correct 144 ms 26168 KB Output is correct
7 Correct 232 ms 26664 KB Output is correct
8 Correct 224 ms 27404 KB Output is correct
9 Correct 236 ms 25468 KB Output is correct
10 Correct 240 ms 27944 KB Output is correct
11 Correct 224 ms 25776 KB Output is correct
12 Correct 252 ms 27964 KB Output is correct
13 Correct 188 ms 25700 KB Output is correct
14 Correct 252 ms 28748 KB Output is correct
15 Correct 252 ms 28008 KB Output is correct
16 Correct 200 ms 27532 KB Output is correct
17 Correct 188 ms 25616 KB Output is correct
18 Correct 180 ms 26016 KB Output is correct