Submission #695367

#	Time	Username	Problem	Language	Result	Execution time	Memory
695367		vjudge1	Pipes (BOI13_pipes)	C++14	71.48 / 100	223 ms	28600 KiB

pipes

#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;
}

• Subtask 1: 30 / 30
• Subtask 2: 41.48148148148148 / 70