oj.uz

Submission #17573

# Submission time Handle Problem Language Result Execution time Memory
17573 2015-12-28T08:50:28 Z dohyun0324 전압 (JOI14_voltage) C++
100 / 100
 143 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);
    }
    for(i=1;i<=n;i++)
    {
        if(ch[i]) continue;
        dfs(i,0);
        dfs2(i,0);
        ch[i]=2;
    }
    for(i=1;i<=n;i++)
    {
        if(arr2[i]==cnt && arr[i]==0 && ch[i]==1) dap++;
    }
    if(cnt==1) dap++;
    printf("%d",dap);
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9060 KB Output is correct
2 Correct 80 ms 12932 KB Output is correct
3 Correct 44 ms 9060 KB Output is correct
4 Correct 80 ms 14548 KB Output is correct
5 Correct 3 ms 5904 KB Output is correct
6 Correct 65 ms 11080 KB Output is correct
7 Correct 67 ms 16228 KB Output is correct
8 Correct 77 ms 16232 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9060 KB Output is correct
2 Correct 51 ms 16236 KB Output is correct
3 Correct 56 ms 16232 KB Output is correct
4 Correct 1 ms 5508 KB Output is correct
5 Correct 62 ms 11644 KB Output is correct
6 Correct 71 ms 8676 KB Output is correct
7 Correct 89 ms 11944 KB Output is correct
8 Correct 72 ms 13652 KB Output is correct
9 Correct 63 ms 13288 KB Output is correct
10 Correct 65 ms 11608 KB Output is correct
11 Correct 64 ms 8676 KB Output is correct
12 Correct 64 ms 10420 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 10084 KB Output is correct
2 Correct 97 ms 16228 KB Output is correct
3 Correct 0 ms 5508 KB Output is correct
4 Correct 64 ms 12872 KB Output is correct
5 Correct 76 ms 14156 KB Output is correct
6 Correct 81 ms 12544 KB Output is correct
7 Correct 123 ms 12892 KB Output is correct
8 Correct 116 ms 13852 KB Output is correct
9 Correct 112 ms 11464 KB Output is correct
10 Correct 131 ms 14500 KB Output is correct
11 Correct 122 ms 11828 KB Output is correct
12 Correct 128 ms 14524 KB Output is correct
13 Correct 113 ms 11616 KB Output is correct
14 Correct 143 ms 15468 KB Output is correct
15 Correct 120 ms 14576 KB Output is correct
16 Correct 114 ms 14072 KB Output is correct
17 Correct 117 ms 11744 KB Output is correct
18 Correct 100 ms 12120 KB Output is correct