Submission #1266668

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266668		SnowRaven52	Pipes (BOI13_pipes)	C++20	100 / 100	113 ms	21284 KiB

pipes

#include <bits/stdc++.h>
using namespace std;

int main() {
    // freopen("main.in", "r", stdin);
	  // freopen(".out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m; cin >> n >> m;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> eu(m), ev(m);
    vector<vector<pair<int,int>>> g(n);
    for (int e = 0; e < m; e++) {
        int u, v; cin >> u >> v; u--, v--;
        eu[e] = u; ev[e] = v;
        g[u].push_back({v, e});
        g[v].push_back({u, e});
    }

    if (m > n) { cout << 0 << endl; return 0; }

    vector<int> color(n, -1);
    vector<char> seen_e(m, 0), in_comp_v(n, 0), in_comp_e(m, 0);
    vector<long long> w(m, 0);

    auto comp_edges = [&](const vector<int>& nodes) {
        int cnt = 0;
        for (int u : nodes) for (auto [v, e] : g[u]) if (!in_comp_e[e]) { in_comp_e[e] = 1; cnt++; }
        for (int u : nodes) for (auto [v, e] : g[u]) in_comp_e[e] = 0;
        return cnt;
    };

    auto dfs_tree_assign = [&](int root, int banned) {
        vector<tuple<int,int,int>> st;
        st.push_back({root, -1, 0});
        while (!st.empty()) {
            auto [u, pe, s] = st.back(); st.pop_back();
            if (!s) {
                st.push_back({u, pe, 1});
                for (auto [v, e] : g[u]) if (e != pe && e != banned) st.push_back({v, e, 0});
            } else {
                for (auto [v, e] : g[u]) if (e != pe && e != banned) {
                    w[e] = a[v];
                    a[u] -= w[e];
                    a[v] -= w[e];
                }
            }
        }
    };

    auto path_adjust = [&](int s, int t, int banned, long long add) {
        vector<int> par(n, -1), pe(n, -1);
        deque<int> dq; dq.push_back(s); par[s] = s;
        while (!dq.empty() && par[t] == -1) {
            int u = dq.front(); dq.pop_front();
            for (auto [v, e] : g[u]) if (e != banned && par[v] == -1) {
                par[v] = u; pe[v] = e; dq.push_back(v);
            }
        }
        if (par[t] == -1) return false;
        vector<int> path;
        for (int x = t; x != s; x = par[x]) path.push_back(pe[x]);
        reverse(path.begin(), path.end());
        for (int i = 0; i < (int)path.size(); i++) w[path[i]] += (i % 2 == 0 ? add : -add);
        return true;
    };

    for (int i = 0; i < n; i++) if (color[i] == -1) {
        vector<int> nodes, edges;
        queue<int> q;
        color[i] = 0; q.push(i); nodes.push_back(i);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto [v, e] : g[u]) {
                if (!seen_e[e]) { seen_e[e] = 1; edges.push_back(e); }
                if (color[v] == -1) { color[v] = color[u] ^ 1; q.push(v); nodes.push_back(v); }
            }
        }
        int nc = (int)nodes.size();
        int mc = comp_edges(nodes);
        if (mc > nc) { cout << 0 << endl; return 0; }
        for (int u : nodes) in_comp_v[u] = 1;
        if (mc == nc - 1) {
            dfs_tree_assign(i, -1);
            if (a[i] != 0) { cout << 0 << endl; return 0; }
            for (int u : nodes) in_comp_v[u] = 0;
            continue;
        }
        int he = -1;
        for (int e : edges) if (color[eu[e]] == color[ev[e]]) { he = e; break; }
        if (he == -1) { cout << 0 << endl; return 0; }
        int s = eu[he], t = ev[he];
        dfs_tree_assign(s, he);
        long long rem = a[s];
        if (rem & 1LL) { cout << 0 << endl; return 0; }
        long long half = rem / 2;
        if (!path_adjust(s, t, he, half)) { cout << 0 << endl; return 0; }
        w[he] += half;
        for (int u : nodes) in_comp_v[u] = 0;
    }

    for (int e = 0; e < m; e++) cout << (w[e] * 2) << endl;
}

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