Submission #85970

#	Time	Username	Problem	Language	Result	Execution time	Memory
85970		wolfris	Pipes (BOI13_pipes)	C++14	100 / 100	394 ms	33776 KiB

pipes

#include <iostream>

#include <stdio.h>

#include <vector>

#include <queue>



using namespace std;



int n, m, c[100015], adjcnt[100015], p[500000], ncycle, sum, oper = 1;

vector <pair <int, int>> a[100015];

pair <int, int> trace[100015];



bool trim_graph() {

    queue <int> q;

    for (int u = 1; u <= n; ++u)

        if (adjcnt[u] == 1)

            q.push(u);

    while (!q.empty()) {

        int u = q.front(); q.pop();

        --ncycle;

        for (auto e: a[u])

            if (adjcnt[e.first]) {

                int v = e.first;

                --adjcnt[u]; --adjcnt[v];

                p[e.second] = 2 * c[u];

                c[v] -= c[u];

                if (ncycle == 1 && c[v])

                    return false;

                if (adjcnt[v] == 1)

                    q.push(v);

            }

    }

    return true;

}



void dfs(int u) {

    sum += c[u] * oper; oper = -oper;

    for (auto e: a[u])

        if (adjcnt[e.first] == 2) {

            int v = e.first;

            --adjcnt[u]; --adjcnt[v],

            trace[u] = e; dfs(v);

            return;

        }

    for (auto e: a[u])

        if (adjcnt[e.first] == 1) {

            int v = e.first;

            p[e.second] = sum;

            c[u] -= sum / 2;

            c[v] -= sum / 2;

            return;

        }

}



int main() {

    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for (int u = 1; u <= n; ++u)

        cin >> c[u];

    for (int i = 0, u, v; i < m; ++i)

        cin >> u >> v,

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

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

        ++adjcnt[u], ++adjcnt[v];

    if (m > n) goto NO;

    ncycle = n;

    if (!trim_graph()) goto NO;

    if (m == n) {

        if (ncycle % 2 == 0) goto NO;

        int u;

        for (u = 1; u <= n; ++u)

            if (adjcnt[u] == 2) {

                dfs(u); break;

            }

        for (; trace[u].first; u = trace[u].first)

            p[trace[u].second] = 2 * c[u],

            c[trace[u].first] -= c[u];

    }

    for (int i = 0; i < m; ++i)

        cout << p[i] << '\n';

    return 0;

    NO: cout << 0;

}

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