oj.uz

Submission #445039

# Submission time Handle Problem Language Result Execution time Memory
445039 2021-07-16T09:56:23 Z zxcvbnm Pipes (BOI13_pipes) C++14
74.0741 / 100
 202 ms 18112 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxN = 1e5 + 5;
vector<int> need, curr;
vector<pair<int, int>> adj[maxN];
vector<int> in;
vector<int> ans;
void tree(int n) {
    queue<int> q;
    vector<bool> vis(n, false);
    for(int i = 0; i < n; i++) {
        if (in[i] == 1) {
            q.push(i);
        }
    }

    while(!q.empty()) {
        int v = q.front();
        q.pop();
        vis[v] = true;

        for(auto u : adj[v]) {
            if (vis[u.first]) continue;

            ans[u.second] = (need[v] - curr[v]) * 2;
            curr[u.first] += ans[u.second] / 2;
            curr[v] += ans[u.second] / 2;

            in[u.first]--;
            if (in[u.first] == 1) {
                q.push(u.first);
            }
        }
        assert(curr[v] == need[v]);
    }
}
void cant() {
    cout << "0\n";
    exit(0);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    need.resize(n);
    curr.assign(n, 0);
    in.assign(n, 0);
    ans.assign(n, 0);
    for(int& i : need) {
        cin >> i;
    }
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        adj[x].push_back({y, i});
        adj[y].push_back({x, i});
        in[x]++;
        in[y]++;
    }

    if (m == n-1) {
        tree(n);
        for(int i = 0; i < m; i++) {
            cout << ans[i] << "\n";
        }
        exit(0);
    } else if (m != n) {
        cant();
    }

    queue<int> q;
    vector<bool> vis(n, false);
    for(int i = 0; i < n; i++) {
        if (in[i] == 1) {
            q.push(i);
        }
    }

    while(!q.empty()) {
        int v = q.front();
        q.pop();
        vis[v] = true;

        for(auto u : adj[v]) {
            if (vis[u.first]) continue;

            in[u.first]--;
            if (in[u.first] == 1) {
                q.push(u.first);
            }
        }
    }

    // even cycle
    if (count(vis.begin(), vis.end(), false) % 2 == 0) {
        cant();
    }


    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 71 ms 8532 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 54 ms 7308 KB Output is correct
14 Correct 65 ms 8240 KB Output is correct
15 Correct 68 ms 8644 KB Output is correct
16 Correct 59 ms 7688 KB Output is correct
17 Correct 72 ms 8516 KB Output is correct
18 Correct 67 ms 8596 KB Output is correct
19 Correct 68 ms 7860 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2636 KB Output is correct
22 Correct 87 ms 8596 KB Output is correct
23 Correct 51 ms 7364 KB Output is correct
24 Correct 72 ms 8608 KB Output is correct
25 Correct 54 ms 7564 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 2 ms 2636 KB Output isn't correct
3 Correct 51 ms 7472 KB Output is correct
4 Correct 51 ms 7452 KB Output is correct
5 Correct 55 ms 7616 KB Output is correct
6 Correct 202 ms 18112 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Incorrect 2 ms 2536 KB Output isn't correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Incorrect 2 ms 2636 KB Output isn't correct
15 Incorrect 2 ms 2664 KB Output isn't correct
16 Incorrect 2 ms 2636 KB Output isn't correct
17 Correct 2 ms 2636 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 3 ms 2636 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 3 ms 2744 KB Output is correct
22 Incorrect 2 ms 2636 KB Output isn't correct
23 Incorrect 41 ms 6724 KB Output isn't correct
24 Incorrect 52 ms 7644 KB Output isn't correct
25 Correct 54 ms 7564 KB Output is correct
26 Correct 47 ms 7500 KB Output is correct
27 Correct 47 ms 7340 KB Output is correct
28 Correct 50 ms 7748 KB Output is correct
29 Correct 176 ms 15436 KB Output is correct
30 Incorrect 55 ms 7284 KB Output isn't correct
31 Incorrect 51 ms 7464 KB Output isn't correct
32 Incorrect 52 ms 7984 KB Output isn't correct
33 Correct 51 ms 7712 KB Output is correct
34 Correct 48 ms 7356 KB Output is correct
35 Correct 47 ms 7408 KB Output is correct
36 Correct 50 ms 7748 KB Output is correct
37 Correct 190 ms 18056 KB Output is correct
38 Incorrect 51 ms 7492 KB Output isn't correct
39 Incorrect 53 ms 8028 KB Output isn't correct
40 Incorrect 51 ms 7744 KB Output isn't correct
41 Correct 52 ms 7448 KB Output is correct
42 Correct 51 ms 7332 KB Output is correct
43 Correct 48 ms 7276 KB Output is correct
44 Correct 46 ms 7596 KB Output is correct
45 Correct 148 ms 15744 KB Output is correct
46 Incorrect 55 ms 7312 KB Output isn't correct
47 Incorrect 53 ms 7724 KB Output isn't correct
48 Incorrect 55 ms 7448 KB Output isn't correct
49 Correct 52 ms 7748 KB Output is correct
50 Correct 51 ms 7512 KB Output is correct
51 Correct 53 ms 7620 KB Output is correct
52 Correct 50 ms 7364 KB Output is correct
53 Correct 158 ms 15796 KB Output is correct
54 Incorrect 53 ms 7460 KB Output isn't correct