oj.uz

Submission #982582

# Submission time Handle Problem Language Result Execution time Memory
982582 2024-05-14T12:50:42 Z JooDdae 전압 (JOI14_voltage) C++17
100 / 100
 83 ms 22680 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, col[100100], chk[200200];
vector<array<int, 2>> v[100100], odd, even;

int in[100100], out[100100], t[200200], cnt;

void dfs(int u, int p, int pid, int c) {
    col[u] = c, in[u] = ++cnt;

    for(auto [x, id] : v[u]) if(!chk[id]) {
        chk[id] = 1;
        if(col[x] == -1) {
            dfs(x, u, id, c^1);
            continue;
        }

        if(col[x] != c) even.push_back({u, x});
        else odd.push_back({u, x});
    }

    out[u] = ++cnt;
}

void update(int b, int c) {
    while(b <= 2*n) t[b] += c, b += b & -b;
}

int find(int b) {
    int re = 0;
    while(b) re += t[b], b -= b & -b;
    return re;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        int x, y; cin >> x >> y;
        v[x].push_back({y, i}), v[y].push_back({x, i});
    }
    memset(col, -1, sizeof col);
    for(int i=1;i<=n;i++) if(!in[i]) dfs(i, 0, 0, 0), update(in[i], 3*m), update(in[i]+1, -3*m);

    for(auto [x, y] : even) update(in[y]+1, -1), update(in[x]+1, 1);
    for(auto [x, y] : odd) update(in[y]+1, 1), update(in[x]+1, -1);

    int cnt = 0;
    for(int i=2;i<=n;i++) if(find(in[i])-find(out[i]) == odd.size()) cnt++;
    cout << cnt + (odd.size() == 1);
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:51:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i=2;i<=n;i++) if(find(in[i])-find(out[i]) == odd.size()) cnt++;
      |                              ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 10040 KB Output is correct
2 Correct 35 ms 14672 KB Output is correct
3 Correct 23 ms 9932 KB Output is correct
4 Correct 40 ms 16472 KB Output is correct
5 Correct 4 ms 5720 KB Output is correct
6 Correct 33 ms 12632 KB Output is correct
7 Correct 37 ms 18516 KB Output is correct
8 Correct 38 ms 18520 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 9676 KB Output is correct
2 Correct 35 ms 18572 KB Output is correct
3 Correct 28 ms 18512 KB Output is correct
4 Correct 2 ms 5208 KB Output is correct
5 Correct 27 ms 13400 KB Output is correct
6 Correct 31 ms 9820 KB Output is correct
7 Correct 45 ms 13860 KB Output is correct
8 Correct 40 ms 15456 KB Output is correct
9 Correct 35 ms 15492 KB Output is correct
10 Correct 33 ms 13648 KB Output is correct
11 Correct 29 ms 9820 KB Output is correct
12 Correct 40 ms 12116 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 13584 KB Output is correct
2 Correct 48 ms 22680 KB Output is correct
3 Correct 4 ms 4952 KB Output is correct
4 Correct 40 ms 15416 KB Output is correct
5 Correct 39 ms 16980 KB Output is correct
6 Correct 41 ms 15516 KB Output is correct
7 Correct 77 ms 19328 KB Output is correct
8 Correct 82 ms 19796 KB Output is correct
9 Correct 79 ms 17292 KB Output is correct
10 Correct 78 ms 21244 KB Output is correct
11 Correct 66 ms 17612 KB Output is correct
12 Correct 71 ms 21064 KB Output is correct
13 Correct 55 ms 16200 KB Output is correct
14 Correct 71 ms 21712 KB Output is correct
15 Correct 83 ms 21508 KB Output is correct
16 Correct 62 ms 19648 KB Output is correct
17 Correct 63 ms 18888 KB Output is correct
18 Correct 59 ms 18884 KB Output is correct