제출 #755502

#제출 시각아이디문제언어결과실행 시간메모리
755502The_SamuraiPipes (BOI13_pipes)C++17
74.07 / 100
198 ms19272 KiB
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<pair<int, int>>> g(n + 1); vector<int> cnt(n + 1), ans(m), a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; g[u].emplace_back(v, i); g[v].emplace_back(u, i); } if (n < m + 1) { cout << 0; return 0; } queue<int> q; vector<bool> vis(n + 1); for (int i = 1; i <= n; i++) { cnt[i] = g[i].size(); if (cnt[i] == 1) { q.push(i); } } while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = true; for (auto [v, i]: g[u]) { if (vis[v]) continue; cnt[v]--; if (cnt[v] == 1) q.push(v); ans[i] = a[u] * 2; a[v] -= a[u]; } } for (int x: ans) cout << x << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...