제출 #207366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
207366		dolphingarlic	Pipes (BOI13_pipes)	C++14	100 / 100	871 ms	75896 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],A[N],V[N],S=0;void d(int q,int z=1){V[q]=z;for(pair<int,int>i :g[q])if(!V[i.first]){d(i.first,3 - z);if(z == 1)S+=c[i.first];else S-=c[i.first];}}void p(){queue<int>L;FOR(i,1,n+1)if(g[i].size()== 1)L.push(i);while(L.size()){int O=L.front();L.pop();for(pair<int,int>i :g[O]){g[i.first].erase({O,i.second});A[i.second]=2*c[O];c[i.first]-=c[O];if(g[i.first].size()== 1)L.push(i.first);}g[O].clear();}}int main(){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;A[y]=c[i]+S;g[i].erase({x,y});g[x].erase({i,y});c[i]-=A[y]/2;c[x]-=A[y]/2;break;}p();FOR(i,1,m+1)cout<<A[i]<<'\n';return 0;}

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