Submission #695371

# Submission time Handle Problem Language Result Execution time Memory
695371 2023-02-05T04:47:19 Z Duy_e Pipes (BOI13_pipes) C++14
71.4815 / 100
237 ms 23220 KB
#include <bits/stdc++.h>
#define ll long long
#define rep(i, n, m) for (ll i = n; i <= m; i ++)
#define rrep(i, n, m) for (ll i = n; i >= m; i --)
using namespace std;

const long long N = 2e5 + 5;

struct edge {
    int u, v;
    ll val;

    int other(int x) {
        return u ^ v ^ x;
    }

} E[3 * N];

vector <int> d[N];
ll a[N], deg[N], n, m;
bool vis[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, m) {
        cin >> E[i].u >> E[i].v;
        d[E[i].u].push_back(i);
        d[E[i].v].push_back(i);
        deg[E[i].u] ++; deg[E[i].v] ++;
        E[i].val = 0;
    }

    int lef = n;

    queue <int> q;
    rep(i, 1, n) if (d[i].size() == 1)
        q.push(i), deg[i] = 0, vis[i] = true;

    if (n == 2) {
        if (a[1] == a[2]) {
            cout << 2 * a[1] << '\n';
            return 0;
        } else {
            cout << 0 << '\n';
            return 0;
        }
    }

    int lst = -1;

    while (q.size()) {
        int u = q.front(); q.pop();
        lst = u;
        lef --;
        vis[u] = true;
        for (int i: d[u]) {
            int v = E[i].other(u);
            if (vis[v]) continue;
            E[i].val += 2 * a[u];
            a[v] -= a[u];
            -- deg[v];
            if (deg[v] == 1 || (lef == 1 && deg[v] == 0)) {
                q.push(v);
            }
        }
    }

    if (a[lst])
        cout << 0 << '\n';
    else
        rep(i, 1, m) cout << E[i].val << '\n';

    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 5032 KB Output is correct
3 Correct 4 ms 5076 KB Output is correct
4 Correct 101 ms 13000 KB Output is correct
5 Correct 7 ms 5044 KB Output is correct
6 Correct 4 ms 4948 KB Output is correct
7 Correct 3 ms 5036 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 5 ms 5040 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 4 ms 5076 KB Output is correct
12 Correct 4 ms 5036 KB Output is correct
13 Correct 57 ms 11476 KB Output is correct
14 Correct 86 ms 12536 KB Output is correct
15 Correct 97 ms 12948 KB Output is correct
16 Correct 87 ms 11840 KB Output is correct
17 Correct 147 ms 12952 KB Output is correct
18 Correct 65 ms 13056 KB Output is correct
19 Correct 89 ms 12752 KB Output is correct
20 Correct 5 ms 5052 KB Output is correct
21 Correct 4 ms 5040 KB Output is correct
22 Correct 104 ms 12940 KB Output is correct
23 Correct 64 ms 11464 KB Output is correct
24 Correct 88 ms 12996 KB Output is correct
25 Correct 100 ms 11728 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4948 KB Output isn't correct
2 Incorrect 3 ms 5032 KB Output isn't correct
3 Correct 75 ms 12064 KB Output is correct
4 Correct 78 ms 12340 KB Output is correct
5 Correct 78 ms 12360 KB Output is correct
6 Correct 237 ms 23216 KB Output is correct
7 Incorrect 4 ms 5032 KB Output isn't correct
8 Incorrect 5 ms 5032 KB Output isn't correct
9 Correct 4 ms 5028 KB Output is correct
10 Correct 5 ms 5036 KB Output is correct
11 Correct 4 ms 5032 KB Output is correct
12 Correct 3 ms 5020 KB Output is correct
13 Correct 4 ms 5032 KB Output is correct
14 Incorrect 3 ms 5036 KB Output isn't correct
15 Incorrect 4 ms 5076 KB Output isn't correct
16 Incorrect 5 ms 5040 KB Output isn't correct
17 Correct 5 ms 5076 KB Output is correct
18 Correct 8 ms 5088 KB Output is correct
19 Correct 4 ms 5032 KB Output is correct
20 Correct 4 ms 5076 KB Output is correct
21 Correct 5 ms 5076 KB Output is correct
22 Incorrect 4 ms 5076 KB Output isn't correct
23 Incorrect 54 ms 11148 KB Output isn't correct
24 Incorrect 101 ms 12316 KB Output isn't correct
25 Correct 95 ms 12096 KB Output is correct
26 Correct 70 ms 12364 KB Output is correct
27 Correct 65 ms 12256 KB Output is correct
28 Correct 94 ms 12560 KB Output is correct
29 Correct 190 ms 20412 KB Output is correct
30 Incorrect 82 ms 12176 KB Output isn't correct
31 Incorrect 70 ms 12252 KB Output isn't correct
32 Incorrect 68 ms 12536 KB Output isn't correct
33 Correct 83 ms 12344 KB Output is correct
34 Correct 64 ms 12264 KB Output is correct
35 Correct 51 ms 12392 KB Output is correct
36 Correct 69 ms 12456 KB Output is correct
37 Correct 223 ms 23220 KB Output is correct
38 Incorrect 78 ms 12352 KB Output isn't correct
39 Incorrect 88 ms 12608 KB Output isn't correct
40 Incorrect 64 ms 12364 KB Output isn't correct
41 Correct 60 ms 12212 KB Output is correct
42 Correct 70 ms 12264 KB Output is correct
43 Correct 76 ms 12188 KB Output is correct
44 Correct 75 ms 12280 KB Output is correct
45 Incorrect 178 ms 21260 KB Output isn't correct
46 Incorrect 76 ms 12364 KB Output isn't correct
47 Incorrect 93 ms 12332 KB Output isn't correct
48 Incorrect 72 ms 12332 KB Output isn't correct
49 Correct 58 ms 12108 KB Output is correct
50 Correct 78 ms 12368 KB Output is correct
51 Correct 66 ms 12496 KB Output is correct
52 Correct 61 ms 12168 KB Output is correct
53 Incorrect 209 ms 21704 KB Output isn't correct
54 Incorrect 114 ms 12264 KB Output isn't correct