Submission #695367

# Submission time Handle Problem Language Result Execution time Memory
695367 2023-02-05T04:45:10 Z vjudge1 Pipes (BOI13_pipes) C++14
71.4815 / 100
223 ms 28600 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 5040 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5076 KB Output is correct
4 Correct 85 ms 13744 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5052 KB Output is correct
10 Correct 3 ms 5076 KB Output is correct
11 Correct 4 ms 5040 KB Output is correct
12 Correct 3 ms 5076 KB Output is correct
13 Correct 59 ms 11820 KB Output is correct
14 Correct 72 ms 13124 KB Output is correct
15 Correct 65 ms 13736 KB Output is correct
16 Correct 49 ms 12328 KB Output is correct
17 Correct 69 ms 13628 KB Output is correct
18 Correct 72 ms 13736 KB Output is correct
19 Correct 64 ms 13360 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 4 ms 5076 KB Output is correct
22 Correct 73 ms 13708 KB Output is correct
23 Correct 65 ms 11812 KB Output is correct
24 Correct 79 ms 13688 KB Output is correct
25 Correct 60 ms 12192 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5036 KB Output isn't correct
2 Incorrect 3 ms 5044 KB Output isn't correct
3 Correct 54 ms 12584 KB Output is correct
4 Correct 69 ms 12984 KB Output is correct
5 Correct 76 ms 13012 KB Output is correct
6 Correct 223 ms 28600 KB Output is correct
7 Incorrect 3 ms 5032 KB Output isn't correct
8 Incorrect 4 ms 4948 KB Output isn't correct
9 Correct 3 ms 5036 KB Output is correct
10 Correct 4 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 5028 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Incorrect 4 ms 4948 KB Output isn't correct
15 Incorrect 3 ms 5076 KB Output isn't correct
16 Incorrect 4 ms 5040 KB Output isn't correct
17 Correct 3 ms 5076 KB Output is correct
18 Correct 5 ms 5080 KB Output is correct
19 Correct 3 ms 5076 KB Output is correct
20 Correct 3 ms 5048 KB Output is correct
21 Correct 4 ms 5108 KB Output is correct
22 Incorrect 3 ms 5044 KB Output isn't correct
23 Incorrect 54 ms 11520 KB Output isn't correct
24 Incorrect 53 ms 13116 KB Output isn't correct
25 Correct 73 ms 12596 KB Output is correct
26 Correct 65 ms 13060 KB Output is correct
27 Correct 67 ms 12888 KB Output is correct
28 Correct 61 ms 13260 KB Output is correct
29 Correct 175 ms 24544 KB Output is correct
30 Incorrect 58 ms 12728 KB Output isn't correct
31 Incorrect 62 ms 13004 KB Output isn't correct
32 Incorrect 72 ms 13124 KB Output isn't correct
33 Correct 47 ms 13044 KB Output is correct
34 Correct 49 ms 13028 KB Output is correct
35 Correct 56 ms 13004 KB Output is correct
36 Correct 84 ms 13144 KB Output is correct
37 Correct 194 ms 28468 KB Output is correct
38 Incorrect 60 ms 13036 KB Output isn't correct
39 Incorrect 54 ms 13188 KB Output isn't correct
40 Incorrect 67 ms 13104 KB Output isn't correct
41 Correct 58 ms 12880 KB Output is correct
42 Correct 59 ms 12848 KB Output is correct
43 Correct 48 ms 12972 KB Output is correct
44 Correct 64 ms 13000 KB Output is correct
45 Incorrect 156 ms 25540 KB Output isn't correct
46 Incorrect 78 ms 12960 KB Output isn't correct
47 Incorrect 57 ms 13104 KB Output isn't correct
48 Incorrect 56 ms 12952 KB Output isn't correct
49 Correct 54 ms 12784 KB Output is correct
50 Correct 52 ms 13028 KB Output is correct
51 Correct 67 ms 13100 KB Output is correct
52 Correct 54 ms 12912 KB Output is correct
53 Incorrect 175 ms 26268 KB Output isn't correct
54 Incorrect 74 ms 12860 KB Output isn't correct