Submission #535159

#	Time	Username	Problem	Language	Result	Execution time	Memory
535159		faik	Pipes (BOI13_pipes)	C++14	36.30 / 100	81 ms	12936 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

#define MOD 998244353
#define INF 1000000001
#define LNF 1000000000000000001

#define int ll

typedef long long ll;
typedef pair<int,int> pii;

void solve(){
//#define TEST
	int n,m;cin >> n >> m;
	if(m > n){
		cout << "0";
		return;
	}
	vector<int> net(n);
	for(int i = 0;i < n;i++){
		cin >> net[i];
	}
	vector<int> ret(m);
	vector<vector<pii>> edge(n);
	for(int i = 0;i < m;i++){
		int a,b;cin >> a >> b;
		edge[a].emplace_back(b,i);
		edge[b].emplace_back(a,i);
	}
	stack<int> leaf;
	vector<int> sizes(n);
	vector<int> removed(n);
	for(int i = 0;i < n;i++){
		sizes[i] = edge[i].size();
		if(edge[i].size() == 1){
			leaf.push(i);
		}
	}
	while(!leaf.empty()){	
		int top = leaf.top();
		leaf.pop();
		removed[top] = true;
		pii parent;
		for(auto i : edge[top]){
			if(!removed[i.first])
				parent = i;
		}
		ret[parent.second] = -net[top]*2;
		sizes[top]--;
		sizes[parent.first]--;
		if(sizes[parent.first] == 1){
			leaf.push(parent.first);
		}
	}
	int left = 0;
	for(int i = 0;i < n;i++){
		if(!removed[i])
			left++;
	}
	if(left == 0){
		for(int i : ret)
			cout << i << ' ';
		return;
	} else if(left%2 == 0){
		cout << '0';
		return;
	}
	
	
	
}

signed main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
#ifdef DEBUG
	freopen("i.txt","r",stdin);
	freopen("o.txt","w",stdout);
#endif
	int t = 1;
#ifdef TEST
	cin >> t;
#endif
	while(t--){
		solve();
	}

	return 0;
}

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