Submission #84231

#	Time	Username	Problem	Language	Result	Execution time	Memory
84231		atoiz	Pipes (BOI13_pipes)	C++14	100 / 100	121 ms	24452 KiB

pipes

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <stack>

using namespace std;

const int MAX_N = 100010, MAX_M = 500100;
bool dead[MAX_N];
vector<int> G[MAX_N];
int deg[MAX_N];
struct Edge { int u, v; } edges[MAX_M];
int n, m;
int64_t w_e[MAX_M], w_v[MAX_N], nxt_id[MAX_N];

void kill() { cout << 0; exit(0); }

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    if (m > n) kill();

    for (int u = 1; u <= n; ++u) cin >> w_v[u];
    for (int id = 0; id < m; ++id) {
        int u, v; cin >> u >> v;
        ++deg[u], ++deg[v];
        G[u].push_back(id); G[v].push_back(id);
        edges[id] = {u, v};
    }

    stack<int> st;
    for (int u = 1; u <= n; ++u) if (deg[u] == 1) st.push(u);
    while (!st.empty()) {
        int u = st.top(); st.pop();
		dead[u] = 1;
        for (int id : G[u]) {
            int v = edges[id].u == u ? edges[id].v : edges[id].u;
            if (dead[v]) continue;

            w_e[id] = w_v[u];
            w_v[u] -= w_e[id]; w_v[v] -= w_e[id];
            --deg[u]; --deg[v];

            if (deg[v] == 1) st.push(v);
        }
    }

    if (m < n) {
        for (int i = 0; i < m; ++i) cout << w_e[i] * 2 << '\n';
        return 0;
    }

    int start = 1;
    while (dead[start]) ++start;
	int u = start, p = -1, cnt = 0;
	int64_t cur = 0, sgn = 1;
    do {
        cur += w_v[u] * sgn; sgn = -sgn;

		int v;
        for (int id : G[u]) {
            v = edges[id].u == u ? edges[id].v : edges[id].u;
            if (p == v) continue;
            if (!dead[v]) {
                nxt_id[u] = id;
				break;
            }
        }
		p = u, u = v;
		++cnt;
    } while (u != start);

    if (!(cnt & 1)) kill();
    if (cur & 1) kill();
    cur >>= 1;

    u = start;
    do {
        cur = w_v[u] - cur;
        int id = nxt_id[u];
        w_e[id] = cur;
        u = edges[id].u == u ? edges[id].v : edges[id].u;
    } while (u != start);

	for (int i = 0; i < m; ++i) cout << w_e[i] * 2 << '\n';
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:86:16: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
     } while (u != start);
              ~~^~~~~~~~

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