Submission #207363

#	Time	Username	Problem	Language	Result	Execution time	Memory
207363		dolphingarlic	Pipes (BOI13_pipes)	C++14	100 / 100	572 ms	76044 KiB

pipes

#include <bits/stdc++.h>
#define FOR(i,x,y) for (int i=x;i < y;i++)
using namespace std;const int N=6e5;int n,m;set<pair<int,int>> g[N];int c[N],ans[N],visited[N],S=0;void d(int node,int parity=1) {visited[node]=parity;for (pair<int,int> i : g[node]) if (!visited[i.first]) {d(i.first,3 - parity);if (parity == 1) S += c[i.first];else S -= c[i.first];}}void p() {queue<int> leaves;FOR(i,1,n + 1) if (g[i].size() == 1) leaves.push(i);while (leaves.size()) {int curr=leaves.front();leaves.pop();for (pair<int,int> i : g[curr]) {g[i.first].erase({curr,i.second});ans[i.second]=2 * c[curr];c[i.first] -= c[curr];if (g[i.first].size() == 1) leaves.push(i.first);}g[curr].clear();}}int main() {iostream::sync_with_stdio(false);cin.tie(0);cin >> n >> m;FOR(i,1,n + 1) cin >> c[i];FOR(i,1,m + 1) {int x,y;cin >> x >> y;g[x].insert({y,i});g[y].insert({x,i});}p();int cnt=0;FOR(i,1,n + 1) {if (g[i].size() > 2) return cout << 0,0;if (g[i].size() == 2) cnt++;}if (cnt != 0 && !(cnt & 1)) return cout << 0,0;FOR(i,1,n + 1) if (g[i].size() == 2) {d(i);int x=(*g[i].begin()).first,y=(*g[i].begin()).second;ans[y]=c[i] + S;g[i].erase({x,y});g[x].erase({i,y});c[i] -= ans[y] / 2;c[x] -= ans[y] / 2;break;}p();FOR(i,1,m + 1) cout << ans[i] << '\n';return 0;}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70