oj.uz

Submission #129776

# Submission time Handle Problem Language Result Execution time Memory
129776 2019-07-13T08:11:51 Z 송준혁(#3142) 전압 (JOI14_voltage) C++14
100 / 100
 194 ms 19940 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, M, O, ans;
vector<pii> adj[101010];
int col[101010], id[101010], num=1;
int OS[202020], ES[202020], dep[202020];
int OV[101010], EV[101010];

bool color(int u, int b, int c){
    if (col[u]){
        if (col[u] != c) return false;
        return true;
    }
    col[u] = c;
    for (pii v : adj[u]){
        if (v.second == b){
            if (!color(v.first, b, c)) return false;
        }
        else if (!color(v.first, b, c*-1)) return false;
    }
    return true;
}

void dfs(int u, int p, int d){
    id[u] = num++;
    dep[u] = d;
    for (pii v : adj[u]){
        if (v.second == p || id[v.first] > id[u]) continue;
        if (id[v.first]){
            if ((d - dep[v.first]) & 1){
                ES[v.second]++;
                EV[u]++, EV[v.first]--;
            }
            else{
                OS[v.second]++, O++;
                OV[u]++, OV[v.first]--;
            }
        }
        else {
            dfs(v.first, v.second, d+1);
            OV[u] += OV[v.first];
            EV[u] += EV[v.first];
        }
    }
    OS[p] += OV[u], ES[p] += EV[u];
}

int main(){
    int u, v;
    scanf("%d %d", &N, &M);
    for (int i=1; i<=M; i++){
        scanf("%d %d", &u, &v);
        adj[u].push_back(pii(v, i));
        adj[v].push_back(pii(u, i));
    }
    for (int i=1; i<=N; i++) if (!id[i]) dfs(i, 0, 1);
    bool tf = false;
    for (int i=1; i<=M; i++){
        if (OS[i] == O && !ES[i]){
            tf = true;
            for (int j=1; j<=N; j++) if (!col[j]) tf = tf && color(j, i, 1);
            break;
        }
    }
    if (!tf) puts("0");
    else{
        for (int i=1; i<=M; i++) if (OS[i] == O && !ES[i]) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8684 KB Output is correct
2 Correct 95 ms 13180 KB Output is correct
3 Correct 57 ms 9504 KB Output is correct
4 Correct 93 ms 15568 KB Output is correct
5 Correct 11 ms 3832 KB Output is correct
6 Correct 97 ms 12508 KB Output is correct
7 Correct 103 ms 17196 KB Output is correct
8 Correct 85 ms 16888 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8556 KB Output is correct
2 Correct 52 ms 16384 KB Output is correct
3 Correct 52 ms 16444 KB Output is correct
4 Correct 4 ms 2684 KB Output is correct
5 Correct 78 ms 11740 KB Output is correct
6 Correct 84 ms 10488 KB Output is correct
7 Correct 101 ms 13688 KB Output is correct
8 Correct 106 ms 15060 KB Output is correct
9 Correct 110 ms 15096 KB Output is correct
10 Correct 98 ms 13304 KB Output is correct
11 Correct 90 ms 10360 KB Output is correct
12 Correct 100 ms 12152 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 9700 KB Output is correct
2 Correct 82 ms 17988 KB Output is correct
3 Correct 7 ms 3832 KB Output is correct
4 Correct 114 ms 13560 KB Output is correct
5 Correct 114 ms 16120 KB Output is correct
6 Correct 105 ms 14712 KB Output is correct
7 Correct 172 ms 17868 KB Output is correct
8 Correct 165 ms 18428 KB Output is correct
9 Correct 173 ms 16408 KB Output is correct
10 Correct 189 ms 19508 KB Output is correct
11 Correct 149 ms 16136 KB Output is correct
12 Correct 194 ms 19568 KB Output is correct
13 Correct 135 ms 15596 KB Output is correct
14 Correct 179 ms 19940 KB Output is correct
15 Correct 153 ms 19080 KB Output is correct
16 Correct 146 ms 18288 KB Output is correct
17 Correct 158 ms 16760 KB Output is correct
18 Correct 133 ms 16100 KB Output is correct