Submission #207362

#	Time	Username	Problem	Language	Result	Execution time	Memory
207362		dolphingarlic	Pipes (BOI13_pipes)	C++14	100 / 100	558 ms	58872 KiB

pipes

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m;
set<pair<int, int>> graph[100001];
int c[100001], ans[500001], visited[100001], alt_sum = 0;

void dfs1(int node, int parity = 1) {
    visited[node] = parity;
    for (pair<int, int> i : graph[node]) if (!visited[i.first]) {
        dfs1(i.first, 3 - parity);
        if (parity == 1) alt_sum += c[i.first];
        else alt_sum -= c[i.first];
    }
}

void compress() {
    queue<int> leaves;
    FOR(i, 1, n + 1) if (graph[i].size() == 1) leaves.push(i);
    while (leaves.size()) {
        int curr = leaves.front();
        leaves.pop();
        for (pair<int, int> i : graph[curr]) {
            graph[i.first].erase({curr, i.second});
            ans[i.second] = 2 * c[curr];
            c[i.first] -= c[curr];

            if (graph[i.first].size() == 1) leaves.push(i.first);
        }
        graph[curr].clear();
    }
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    FOR(i, 1, n + 1) cin >> c[i];
    FOR(i, 1, m + 1) {
        int x, y;
        cin >> x >> y;
        graph[x].insert({y, i});
        graph[y].insert({x, i});
    }

    compress();

    int cnt = 0;
    FOR(i, 1, n + 1) {
        if (graph[i].size() > 2) return cout << 0, 0;
        if (graph[i].size() == 2) cnt++;
    }
    if (cnt != 0 && !(cnt & 1)) return cout << 0, 0;

    FOR(i, 1, n + 1) if (graph[i].size() == 2) {
        dfs1(i);
        int x = (*graph[i].begin()).first, y = (*graph[i].begin()).second;
        ans[y] = c[i] + alt_sum;
        graph[i].erase({x, y});
        graph[x].erase({i, y});
        c[i] -= ans[y] / 2;
        c[x] -= ans[y] / 2;
        break;
    }

    compress();

    FOR(i, 1, m + 1) cout << ans[i] << '\n';
    return 0;
}

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