oj.uz

Submission #563935

# Submission time Handle Problem Language Result Execution time Memory
563935 2022-05-18T09:50:09 Z tengiz05 전압 (JOI14_voltage) C++17
100 / 100
 518 ms 42052 KB 
#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    std::vector<std::vector<int>> e(n);
    
    std::map<std::pair<int, int>, int> id, cnt;
    
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        e[u].push_back(v);
        e[v].push_back(u);
        id[std::minmax(u, v)] = i;
        cnt[std::minmax(u, v)]++;
    }
    
    std::vector<int> color(n, -1), p(n), dep(n);
    p[0] = -1;
    std::function<void(int)> dfs = [&](int u) {
        for (int v : e[u]) {
            if (color[v] == -1) {
                p[v] = u;
                dep[v] = dep[u] + 1;
                color[v] = color[u] ^ 1;
                dfs(v);
            }
        }
    };
    for (int i = 0; i < n; i++) {
        if (color[i] == -1) {
            color[i] = 0;
            p[i] = -1;
            dfs(i);
        }
    }
    
    std::vector<int> f(n);
    
    int badEdges = 0;
    for (int u = 0; u < n; u++) {
        for (int v : e[u]) {
            if (dep[u] < dep[v] && p[v] != u) {
                if (color[u] == color[v]) {
                    badEdges++;
                    f[v]++;
                    f[u]--;
                } else {
                    f[v]--;
                    f[u]++;
                }
            }
        }
    }
    
    std::vector<bool> vis(n);
    dfs = [&](int u) {
        vis[u] = true;
        for (int v : e[u]) {
            if (p[v] == u && !vis[v]) {
                dfs(v);
                f[u] += f[v];
            }
        }
    };
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            dfs(i);
        }
    }
    
    std::vector<int> ans;
    
    if (badEdges == 1) {
        for (auto [p, i] : id) {
            if (color[p.first] == color[p.second] && cnt[std::minmax(p.first, p.second)] == 1) {
                ans.push_back(i);
            }
        }
    }
    
    for (int i = 1; i < n; i++) {
        if (f[i] == badEdges && cnt[std::minmax(p[i], i)] == 1) {
            ans.push_back(id[std::minmax(p[i], i)]);
        }
    }
    
    std::sort(ans.begin(), ans.end());
    std::cout << ans.size() << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t = 1;
    // std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 2 ms 712 KB Output is correct
8 Correct 2 ms 452 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 3 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 22156 KB Output is correct
2 Correct 292 ms 26200 KB Output is correct
3 Correct 177 ms 21552 KB Output is correct
4 Correct 216 ms 27192 KB Output is correct
5 Correct 14 ms 2900 KB Output is correct
6 Correct 228 ms 24196 KB Output is correct
7 Correct 287 ms 29428 KB Output is correct
8 Correct 188 ms 28864 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 21824 KB Output is correct
2 Correct 103 ms 29512 KB Output is correct
3 Correct 102 ms 29488 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 189 ms 21096 KB Output is correct
6 Correct 250 ms 21904 KB Output is correct
7 Correct 246 ms 25312 KB Output is correct
8 Correct 199 ms 26396 KB Output is correct
9 Correct 244 ms 26444 KB Output is correct
10 Correct 198 ms 24420 KB Output is correct
11 Correct 178 ms 21092 KB Output is correct
12 Correct 196 ms 23116 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 22116 KB Output is correct
2 Correct 125 ms 29988 KB Output is correct
3 Correct 28 ms 10428 KB Output is correct
4 Correct 246 ms 27032 KB Output is correct
5 Correct 251 ms 28568 KB Output is correct
6 Correct 216 ms 26572 KB Output is correct
7 Correct 477 ms 38448 KB Output is correct
8 Correct 480 ms 39804 KB Output is correct
9 Correct 457 ms 37948 KB Output is correct
10 Correct 419 ms 40908 KB Output is correct
11 Correct 477 ms 35772 KB Output is correct
12 Correct 455 ms 40928 KB Output is correct
13 Correct 333 ms 27608 KB Output is correct
14 Correct 518 ms 42052 KB Output is correct
15 Correct 464 ms 40960 KB Output is correct
16 Correct 448 ms 35648 KB Output is correct
17 Correct 421 ms 40108 KB Output is correct
18 Correct 253 ms 22144 KB Output is correct