oj.uz

Submission #129775

# Submission time Handle Problem Language Result Execution time Memory
129775 2019-07-13T08:10:42 Z 송준혁(#3142) 전압 (JOI14_voltage) C++14
10 / 100
 110 ms 17656 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[1010];

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 4 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 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 3 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 5 ms 2812 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 6 ms 2936 KB Output is correct
12 Correct 5 ms 2912 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8568 KB Output is correct
2 Correct 51 ms 15992 KB Output is correct
3 Correct 54 ms 15964 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Incorrect 90 ms 11932 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 9828 KB Output is correct
2 Correct 82 ms 17656 KB Output is correct
3 Correct 7 ms 3960 KB Output is correct
4 Incorrect 107 ms 13304 KB Output isn't correct
5 Halted 0 ms 0 KB -