Submission #1077640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077640		ShadowShark	Pipes (BOI13_pipes)	C++17	100 / 100	135 ms	19404 KiB

pipes

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

const int maxN = 1e5 + 5;
long long c[maxN];
vector<pair<int, int>> adj[maxN];
int n, m;

namespace sub1 {
    long long ans[maxN];

    void dfs(int u, int pre) {
        for (auto [v, id]: adj[u]) {
            if (v == pre) continue;
            dfs(v, u);
            ans[id] += 2 * c[v];
            c[u] -= c[v];
        }
    }

    void solve() {
        dfs(1, 1);

        for (int i = 1; i <= m; i++)
            cout << ans[i] << '\n';
    }
}

namespace even_cycle {
    bool even_exist = false; int color[maxN];

    void dfs(int u, int pre) {
        for (auto [v, id]: adj[u]) {
            if (v == pre) continue;
            if (color[v]) {
                if (color[v] != color[u]) even_exist = true;
                continue;
            }
            color[v] = 3 - color[u];
            dfs(v, u);
        }
    }

    bool check() {
        color[1] = 1;
        dfs(1, 1);
        if (even_exist) return true;
        return false;
    }
}

namespace sub2 {
    long long ans[maxN];
    bool visited[maxN], cycle[maxN];
    int nxt[maxN], par[maxN];
    vector<int> edge, node;

    bool dfs_cycle(int u, int pre) {
        visited[u] = true;
        for (auto [v, id]: adj[u]) {
            if (v == pre) continue;
            if (visited[v]) {
                int x = u;
                edge.push_back(id);
                node.push_back(u);
                cycle[u] = true;
                do {
                    edge.push_back(nxt[x]);
                    node.push_back(par[x]);
                    cycle[par[x]] = true;
                    x = par[x];
                } while (x != v);
                return true;
            }
            par[v] = u;
            nxt[v] = id;
            if (dfs_cycle(v, u)) return true;
        }
        return false;
    }

    void dfs_cal(int u, int pre) {
        for (auto [v, id]: adj[u]) {
            if (v == pre || cycle[v]) continue;
            dfs_cal(v, u);
            ans[id] = 2 * c[v];
            c[u] -= c[v];
        }
    }

    void solve() {
        dfs_cycle(1, 1);

        for (int i = 1; i <= n; i++)
            if (cycle[i]) dfs_cal(i, i);

        long long res = 0;
        for (int i = 0; i < node.size(); i++)
            if (i % 2) res = res - c[node[i]];
                else res = res + c[node[i]];

        for (int i = 0; i < edge.size(); i++) {
            ans[edge[i]] = res;
            res -= 2 * c[node[i]];
            res = res * -1;
        }

        for (int i = 1; i <= m; i++)
            cout << ans[i] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        cin >> c[i];

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    if (m == n - 1) sub1::solve();
        else if (m > n || even_cycle::check()) {
            cout << 0;
            return 0;
        }
        else sub2::solve();

    return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'void sub2::solve()':
pipes.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int i = 0; i < node.size(); i++)
      |                         ~~^~~~~~~~~~~~~
pipes.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (int i = 0; i < edge.size(); i++) {
      |                         ~~^~~~~~~~~~~~~

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