제출 #1051109

#제출 시각아이디문제언어결과실행 시간메모리
1051109ortsacPipes (BOI13_pipes)C++17
44.07 / 100
1 ms3592 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<long long, long long> #define fr first #define se second const int MAXN = 1e5 + 10; const int MAXM = 5e5 + 10; vector<pii> adj[MAXN]; int bEdge = -1; vector<pii> edges; int h[MAXN]; int change[MAXN]; bool vis[MAXN]; int dad[MAXN]; int dp[MAXN]; int peso[MAXM]; void dfs(int node) { vis[node] = 1; for (auto [u, z] : adj[node]) { if (u == dad[node]) continue; if (vis[u]) bEdge = z; else { dad[u] = node; h[u] = h[node] + 1; dfs(u); } } } void calc(int node) { vis[node] = 1; for (auto [u, z] : adj[node]) { if (vis[u]) continue; calc(u); dp[node] += (change[u] - dp[u]); peso[z] += (change[u] - dp[u]); } } vector<int> path; bool found = 0; int need; void cPath(int node, int wantNode) { vis[node] = 1; path.push_back(node); if (node == wantNode) { found = 1; return; } for (auto [u, z] : adj[node]) { if (vis[u]) continue; cPath(u, wantNode); if (found) return; } path.pop_back(); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cout << 0 << "\n"; return 0; int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) cin >> change[i]; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; edges.push_back({a, b}); adj[a].push_back({b, i}); adj[b].push_back({a, i}); } if (m > n) { cout << "0\n"; return 0; } dfs(1); int lca = 0; if (bEdge != -1) { auto u = edges[bEdge]; int a = u.fr, b = u.se; if (h[a] > h[b]) swap(a, b); // a is higher than b int oa = a, ob = b; while (h[b] > h[a]) { b = dad[b]; } while (a != b) { a = dad[a]; b = dad[b]; } lca = a; a = oa; b = ob; int tam = h[a] + h[b] - 2*h[lca] + 1; if ((tam % 2LL) == 0) { cout << "0\n"; return 0; } } memset(vis, 0, sizeof vis); calc(1); if (dp[1] == change[1]) { for (int i = 0; i < m; i++) cout << 2*peso[i] << "\n"; return 0; } // first case is for tree // second case is if you can't add 2x to it if ((bEdge == -1) || ((change[1] - dp[1]) % 2LL)) { cout << "0\n"; return 0; } need = (change[1] - dp[1])/2LL; for (int i = 0; i < m; i++) { cout << 2*peso[i] << "\n"; } memset(vis, 0, sizeof vis); cPath(1, lca); int tam = path.size(); int inv = 1; for (int i = 0; i < (tam - 1); i++) { int node = path[i]; int prox = path[i + 1]; for (auto [u, z] : adj[node]) { if (u == prox) { peso[z] += 2*need*inv; inv = -inv; break; } } } int a = edges[bEdge].fr, b = edges[bEdge].se; path.clear(); memset(vis, 0, sizeof vis); cPath(lca, a); tam = path.size(); int cr = inv; for (int i = 0; i < (tam - 1); i++) { int node = path[i]; int prox = path[i + 1]; for (auto [u, z] : adj[node]) { if (u == prox) { peso[z] += need*cr; cr = -cr; break; } } } path.clear(); memset(vis, 0, sizeof vis); cPath(lca, b); tam = path.size(); cr = inv; for (int i = 0; i < (tam - 1); i++) { int node = path[i]; int prox = path[i + 1]; for (auto [u, z] : adj[node]) { if (u == prox) { peso[z] += need*cr; cr = -cr; break; } } } if ((h[a] - h[lca]) % 2LL) inv = -inv; peso[bEdge] += inv*need; for (int i = 0; i < m; i++) { cout << 2*peso[i] << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...