oj.uz

Submission #17572

# Submission time Handle Problem Language Result Execution time Memory
17572 2015-12-28T08:42:47 Z dohyun0324 전압 (JOI14_voltage) C++
45 / 100
 86 ms 16236 KB 
#include<stdio.h>
#include<vector>
using namespace std;
vector<int>con[100010];
int cnt,n,m,ch[100010],lev[100010],arr2[100010],arr[100010],dap,ch2[100010];
void dfs(int x,int bef)
{
    int i,sw=0;
    ch[x]=1;
    for(i=0;i<con[x].size();i++){
        if(con[x][i]==bef && sw==0){sw=1; continue;}
        if(ch[con[x][i]]){
            if(lev[x]<lev[con[x][i]]) continue;
            if((lev[x]-lev[con[x][i]])%2==1) arr[x]++, arr[con[x][i]]--;
            else arr2[x]++, arr2[con[x][i]]--, cnt++;
            continue;
        }
        lev[con[x][i]]=lev[x]+1;
        dfs(con[x][i],x);
    }
}
void dfs2(int x,int bef)
{
    int i,sw=0;
    ch2[x]=1;
    for(i=0;i<con[x].size();i++){
        if(con[x][i]==bef && sw==0){sw=1; continue;}
        if(ch2[con[x][i]]) continue;
        dfs2(con[x][i],x);
        arr[x]+=arr[con[x][i]];
        arr2[x]+=arr2[con[x][i]];
    }
}
int main()
{
    int i,x,y;
    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);
    }
    dfs(1,0);
    dfs2(1,0);
    for(i=2;i<=n;i++){
        if(arr2[i]==cnt && arr[i]==0) dap++;
    }
    if(cnt==1) dap++;
    printf("%d",dap);
    return 0;
}

Subtask #1
0.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 9060 KB Output is correct
2 Correct 86 ms 12932 KB Output is correct
3 Correct 45 ms 9060 KB Output is correct
4 Correct 82 ms 14544 KB Output is correct
5 Correct 8 ms 5908 KB Output is correct
6 Correct 66 ms 11076 KB Output is correct
7 Correct 79 ms 16232 KB Output is correct
8 Correct 70 ms 16228 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 9060 KB Output is correct
2 Correct 35 ms 16236 KB Output is correct
3 Correct 45 ms 16232 KB Output is correct
4 Correct 0 ms 5508 KB Output is correct
5 Correct 56 ms 11648 KB Output is correct
6 Correct 61 ms 8676 KB Output is correct
7 Correct 60 ms 11944 KB Output is correct
8 Correct 67 ms 13652 KB Output is correct
9 Correct 58 ms 13288 KB Output is correct
10 Correct 64 ms 11612 KB Output is correct
11 Correct 59 ms 8676 KB Output is correct
12 Correct 65 ms 10424 KB Output is correct

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 10084 KB Output is correct
2 Correct 56 ms 16232 KB Output is correct
3 Incorrect 0 ms 5508 KB Output isn't correct
4 Halted 0 ms 0 KB -