Submission #1108347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108347		Kirill22	Pipes (BOI13_pipes)	C++17	100 / 100	146 ms	35172 KiB

pipes

#include "bits/stdc++.h"
 
using namespace std;
 
//#include "debug.h"
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0, x, y; i < m; i++) {
        cin >> x >> y;
        x--, y--;
        g[x].push_back({y, i});
        g[y].push_back({x, i});
    }
    vector<pair<int, int>> cycle, par(n);
    vector<int> usd(n), h2(n);
    auto bfs = [&] (auto&& bfs, int v, int pr) -> void {
        usd[v] = 1;
        for (auto [u, i] : g[v]) {
            if (!cycle.empty()) {
                break;
            }
            if (!usd[u]) {
                par[u] = {v, i};
                h2[u] = h2[v] + 1;
                bfs(bfs, u, v);
            } else if (u != pr && h2[v] % 2 == h2[u] % 2) {
                cycle.push_back({v, i});
                while (v != u) {
                    cycle.push_back(par[v]);
                    v = par[v].first;
                }
                std::reverse(cycle.begin(), cycle.end());
            }
        }
    };
    bfs(bfs, 0, 0);
    vector<long long> have(n), ans(m);
    vector<int> used(n), h(n);
    bool ok = true;
    auto dfs = [&] (auto&& dfs, int v, int pr) -> void {
        used[v] = 1;
        for (auto [u, i] : g[v]) {
            if (!used[u]) {
                h[u] = h[v] + 1;
//                cout << v << " " << u << endl;
                dfs(dfs, u, v);
//                cout << u << " " << a[u] << " " << have[u] << endl;
                ans[i] = a[u] - have[u];
                have[u] += ans[i];
                have[v] += ans[i];
            } else if (u != pr && h[v] % 2 != h[u] % 2) {
                ok = false;
            }
        }
    };
    if (cycle.empty()) {
        dfs(dfs, 0, 0);
        if (!ok) {
            cout << 0 << '\n';
            return;
        }
        assert(a == have);
        long long mx = 0;
        for (auto& x : ans) {
            mx = max(mx, abs(x) * 2);
        }
        if (mx > (long long) 1e9) {
            assert(false);
            cout << 0 << '\n';
            return;
        }
        for (int i = 0; i < m; i++) {
            cout << 2 * ans[i] << '\n';
        }
    } else {
        int rt = cycle[0].first;
        dfs(dfs, rt, rt);
//        debug(have);
        if (have[rt] != a[rt]) {
            assert(abs(a[rt] - have[rt]) % 2 == 0);
            long long val = (a[rt] - have[rt]) / 2;
//            cout << val << endl;
            ans[cycle.back().second] += val;
            have[cycle.back().first] += val;
            have[cycle[0].first] += val;
//            debug(have, cycle);
//            for (auto [x, y] : cycle) cout << x << " " << y << endl;
            for (int i = 0; i + 1 < (int) cycle.size(); i++) {
                ans[cycle[i].second] += i % 2 == 0 ? val : -val;
                have[cycle[i].first] += i % 2 == 0 ? val : -val;
                have[cycle[i + 1].first] += i % 2 == 0 ? val : -val;
//                debug(have);
            }
        }
//        debug(have, a);
        assert(have == a);
        if (!ok || m > n) {
//            assert(false);
            cout << 0 << '\n';
            return;
        }
        long long mx = 0;
        for (auto& x : ans) {
            mx = max(mx, abs(x) * 2);
        }
        if (mx > (long long) 1e9) {
            cout << 0 << '\n';
            return;
        }
        for (int i = 0; i < m; i++) {
            cout << 2 * ans[i] << '\n';
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

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