oj.uz

Submission #129777

# Submission time Handle Problem Language Result Execution time Memory
129777 2019-07-13T08:13:01 Z 송준혁(#3142) 전압 (JOI14_voltage) C++14
100 / 100
 192 ms 17912 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];

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);
    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:38: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:40: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 2936 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 6 ms 2808 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 5 ms 2808 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8164 KB Output is correct
2 Correct 84 ms 12740 KB Output is correct
3 Correct 55 ms 8424 KB Output is correct
4 Correct 92 ms 14584 KB Output is correct
5 Correct 10 ms 3704 KB Output is correct
6 Correct 78 ms 11512 KB Output is correct
7 Correct 86 ms 16248 KB Output is correct
8 Correct 85 ms 16244 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8172 KB Output is correct
2 Correct 50 ms 15992 KB Output is correct
3 Correct 50 ms 15992 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 67 ms 11364 KB Output is correct
6 Correct 88 ms 9044 KB Output is correct
7 Correct 83 ms 12320 KB Output is correct
8 Correct 80 ms 13636 KB Output is correct
9 Correct 88 ms 13788 KB Output is correct
10 Correct 77 ms 11896 KB Output is correct
11 Correct 81 ms 8952 KB Output is correct
12 Correct 94 ms 10728 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 9704 KB Output is correct
2 Correct 83 ms 17912 KB Output is correct
3 Correct 5 ms 3500 KB Output is correct
4 Correct 84 ms 13356 KB Output is correct
5 Correct 97 ms 14584 KB Output is correct
6 Correct 113 ms 13180 KB Output is correct
7 Correct 155 ms 15736 KB Output is correct
8 Correct 164 ms 16376 KB Output is correct
9 Correct 154 ms 14264 KB Output is correct
10 Correct 192 ms 17272 KB Output is correct
11 Correct 183 ms 14328 KB Output is correct
12 Correct 152 ms 17240 KB Output is correct
13 Correct 128 ms 13336 KB Output is correct
14 Correct 159 ms 17800 KB Output is correct
15 Correct 158 ms 17400 KB Output is correct
16 Correct 145 ms 16232 KB Output is correct
17 Correct 148 ms 14504 KB Output is correct
18 Correct 119 ms 13924 KB Output is correct