Submission #1266665

#TimeUsernameProblemLanguageResultExecution timeMemory
1266665SnowRaven52Pipes (BOI13_pipes)C++20
44.07 / 100
109 ms21584 KiB
#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> s(N + 1); for (int i = 1; i <= N; i++) cin >> s[i]; vector<pair<int,int>> edges(M + 1); vector<vector<pair<int,int>>> adj(N + 1); vector<int> deg(N + 1, 0); for (int i = 1; i <= M; i++) { int u, v; cin >> u >> v; edges[i] = {u, v}; adj[u].push_back({v, i}); adj[v].push_back({u, i}); deg[u]++; deg[v]++; } if (M > N) { cout << 0 << endl; return 0; } vector<char> deadE(M + 1, 0), deadV(N + 1, 0); vector<long long> w(M + 1, 0); queue<int> q; for (int i = 1; i <= N; i++) if (deg[i] == 1) q.push(i); while (!q.empty()) { int v = q.front(); q.pop(); if (deadV[v]) continue; int eid = -1, u = -1; for (auto [to, e] : adj[v]) if (!deadE[e]) { u = to; eid = e; break; } if (eid == -1) { deadV[v] = 1; continue; } w[eid] = s[v]; s[u] -= w[eid]; deadE[eid] = 1; deg[v]--; deg[u]--; deadV[v] = 1; if (deg[u] == 1) q.push(u); } int aliveE = 0, start = -1, aliveV = 0; for (int e = 1; e <= M; e++) if (!deadE[e]) aliveE++; for (int i = 1; i <= N; i++) if (!deadV[i] && deg[i] > 0) { aliveV++; if (start == -1) start = i; } if (aliveE == 0) { for (int i = 1; i <= M; i++) cout << w[i] << endl; return 0; } for (int i = 1; i <= N; i++) if (!deadV[i] && deg[i] != 2) { cout << 0 << '\n'; return 0; } if (aliveE != aliveV) { cout << 0 << endl; return 0; } vector<int> cycV, cycE; int v = start, prev = -1, cntE = 0; do { cycV.push_back(v); int ne = -1, nv = -1; for (auto [to, e] : adj[v]) if (!deadE[e] && e != prev) { ne = e; nv = to; break; } if (ne == -1) { cout << 0 << endl; return 0; } cycE.push_back(ne); prev = ne; v = nv; cntE++; } while (v != start && cntE <= aliveE); if (v != start || (int)cycE.size() != aliveE) { cout << 0 << '\n'; return 0; } int K = (int)cycV.size(); if (K % 2 == 0) { cout << 0 << endl; return 0; } long long alt = 0; for (int i = 0; i < K; i++) alt += (i % 2 ? -s[cycV[i]] : s[cycV[i]]); long long lastW = alt / 2; w[cycE.back()] = lastW; long long prevW = lastW; for (int i = 0; i < K - 1; i++) { long long curW = s[cycV[i]] - prevW; w[cycE[i]] = curW; prevW = curW; } for (int i = 1; i <= M; i++) cout << w[i] << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...