Submission #535248

#	Time	Username	Problem	Language	Result	Execution time	Memory
535248		faik	Pipes (BOI13_pipes)	C++14	44.07 / 100	89 ms	13940 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;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]--;
		net[parent.first] -= net[top];
		if(sizes[parent.first] == 1){
			leaf.push(parent.first);
		}
	}
	int left = 0;
	vector<int> cycle;
	for(int i = 0;i < n;i++){
		if(!removed[i]){
			left++;
			cycle.push_back(i);
		}
	}
	if(left == 0){
		for(int i : ret)
			cout << i << ' ';
		return;
	} else if(left%2 == 0){
		cout << '0';
		return;
	}

	int curr = cycle[0];
	int next;int nextRet;
	for(auto i : edge[curr]){
		if(!removed[i.first]){
			next = i.first;
			nextRet = i.second;
		}
	}
	ret[nextRet] += 2*net[cycle[0]];
	net[next] -= net[cycle[0]];
	net[cycle[0]] = 0;
	int last = cycle[0];
	curr = next;

	while(curr != cycle[0]){
		pii next1;
		for(auto i : edge[curr]){
			if(!removed[i.first] && i.first != last){
				next1 = i;
			}	
		}
		ret[next1.second] += 2*net[curr];
		// cout << next1.second << ' ' << 2*net[curr] << '\n';
		net[next1.first] -= net[curr];
		net[curr] = 0;
		last = curr;
		curr = next1.first;
	}

	last = cycle[0];
	curr = next;
	int bruh = next;
	int plus = -1;

	bool cum = false;
	// cout << '*';
	// cout << net[cycle[0]];
	while(curr != next || !cum){
		pii next1;
		for(auto i : edge[curr]){
			if(!removed[i.first] && i.first != last){
				next1 = i;
			}	
		}
		ret[next1.second] += net[cycle[0]]*plus;
		// cout << next1.second << ' ' << net[cycle[0]]*plus << '\n';
		last = curr;
		curr = next1.first;
		plus *= -1;
		cum = true;
	}
	// cout << "\n*";
	for(int i : ret)
		cout << i << ' ';
	// cout << '\n';
	// for(int i : net)
		// cout << i << ' ';
}

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;
}

Compilation message (stderr)

pipes.cpp: In function 'void solve()':
pipes.cpp:108:6: warning: unused variable 'bruh' [-Wunused-variable]
  108 |  int bruh = next;
      |      ^~~~
pipes.cpp:85:13: warning: 'nextRet' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |  ret[nextRet] += 2*net[cycle[0]];
      |             ^
pipes.cpp:114:21: warning: 'next' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |  while(curr != next || !cum){
      |        ~~~~~~~~~~~~~^~~~~~~

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