제출 #802911

#제출 시각아이디문제언어결과실행 시간메모리
802911tch1cherinPipes (BOI13_pipes)C++17
75.37 / 100
194 ms131072 KiB
#include <bits/stdc++.h> using namespace std; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N, M; cin >> N >> M; if (M > N) { cout << 0 << "\n"; exit(0); } vector<int64_t> c(N); for (auto &v : c) { cin >> v; } vector<vector<pair<int, int>>> G(N); vector<int> d(N); for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; u--, v--; d[u]++, d[v]++; G[u].push_back({v, i}); G[v].push_back({u, i}); } vector<int> x(M); queue<int> q; for (int i = 0; i < N; i++) { if (d[i] == 1) { q.push(i); } } vector<bool> used(N); while (!q.empty()) { int u = q.front(); q.pop(); used[u] = true; for (auto [v, i] : G[u]) { if (!used[v]) { x[i] = c[u]; c[v] -= c[u]; d[v]--; if (d[v] == 1) { q.push(v); } } } } if (count(used.begin(), used.end(), false) % 2 == 0 && N == M) { cout << "0\n"; exit(0); } if (N == M) { vector<int> cycle, cycle_edges; for (int i = 0; i < N; i++) { if (!used[i]) { int j = i, last = -1; while (j != i || last == -1) { cycle.push_back(j); for (auto [v, i] : G[j]) { if (v != last) { cycle_edges.push_back(i); last = j; j = v; break; } } } break; } } while (cycle.empty()); int k = (int)cycle.size(); int64_t sum = 0; for (int i = 0; i < k; i++) { sum += c[cycle[i]] * (i % 2 ? -1 : 1); } sum /= 2; x[cycle_edges.back()] = sum; int64_t last = sum; for (int i = 0; i < k - 1; i++) { x[cycle_edges[i]] = c[cycle[i]] - last; last = x[cycle_edges[i]]; } } for (int i = 0; i < M; i++) { cout << x[i] * 2 << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...