Submission #278690

#TimeUsernameProblemLanguageResultExecution timeMemory
278690HynDufPipes (BOI13_pipes)C++14
100 / 100
270 ms18680 KiB
#include <bits/stdc++.h> #define task "P" #define all(v) (v).begin(), (v).end() #define rep(i, l, r) for (int i = (l); i <= (r); ++i) #define Rep(i, r, l) for (int i = (r); i >= (l); --i) #define DB(X) { cerr << #X << " = " << (X) << '\n'; } #define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; } #define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; } #define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; } #define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';} #define SZ(x) ((int)(x).size()) #define pb push_back #define eb emplace_back #define pf push_front #define F first #define S second #define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a)); #define next ___next #define prev ___prev #define y1 ___y1 #define left ___left #define right ___right #define y0 ___y0 #define div ___div #define j0 ___j0 #define jn ___jn using ll = long long; using ld = long double; using ull = unsigned long long; using namespace std; typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<ll> vl; const int N = 1e5 + 2; int n, m, dep[N], deg[N]; ll ans[5 * N], c[N]; vii g[N]; bool dfs(int u, int p) { dep[u] = dep[p] + 1; for (ii v : g[u]) if (v.F != p && dep[v.F] && (dep[u] - dep[v.F]) % 2 == 1) return 1; for (ii v : g[u]) if (v.F != p && !dep[v.F] && dfs(v.F, u)) return 1; return 0; } int main() { #ifdef HynDuf freopen(task".in", "r", stdin); //freopen(task".out", "w", stdout); #else ios_base::sync_with_stdio(false); cin.tie(nullptr); #endif cin >> n >> m; rep(i, 1, n) { cin >> c[i]; c[i] <<= 1; } rep(i, 1, m) { int u, v; cin >> u >> v; g[u].eb(v, i); g[v].eb(u, i); deg[u]++; deg[v]++; } if (dfs(1, 0)) { cout << 0; return 0; } vi st; rep(i, 1, n) if (deg[i] == 1) st.pb(i); while (!st.empty()) { int u = st.back(); st.pop_back(); deg[u]--; for (ii v : g[u]) if (deg[v.F] >= 1 && !ans[v.S]) { ans[v.S] = c[u]; c[v.F] -= c[u]; if (--deg[v.F] == 1) st.pb(v.F); } } rep(i, 1, n) if (deg[i] > 2) { cout << 0; return 0; } rep(i, 1, n) if (deg[i] == 2) { int u = i, lst = 0, cnt = 0; ll sum = 0; while (1) { for (ii v : g[u]) if (deg[v.F] == 2 && v.F != lst) { cnt++; if (cnt & 1) sum += c[u]; else sum -= c[u]; lst = u; u = v.F; break; } if (u == i) break; } ll lstc = sum / 2; u = i, lst = 0; while (1) { for (ii v : g[u]) if (deg[v.F] == 2 && v.F != lst) { ans[v.S] = c[u] - lstc; lstc = ans[v.S]; lst = u; u = v.F; break; } if (u == i) break; } break; } rep(i, 1, m) cout << ans[i] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...