Submission #535377

#	Time	Username	Problem	Language	Result	Execution time	Memory
535377		faik	Pipes (BOI13_pipes)	C++14	100 / 100	93 ms	12240 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> netNodeChange(n);
	for(int i = 0;i < n;i++){
		cin >> netNodeChange[i];
	}

	vector<int> edgeWeight(m);
	vector<vector<pii>> edges(n);
	for(int i = 0;i < m;i++){
		int a,b;cin >> a >> b;a--;b--;
		edges[a].emplace_back(b,i);
		edges[b].emplace_back(a,i);
	}
	//find leafs
	queue<int> leafs;
	vector<int> neighbourCount(n);
	vector<int> removedNodes(n);
	for(int i = 0;i < n;i++){
		neighbourCount[i] = edges[i].size();
		if(edges[i].size() == 1){
			leafs.push(i);
		}
	}
	//remove all leafs
	while(!leafs.empty()){	
		int leaf = leafs.front();
		leafs.pop();
		if(removedNodes[leaf])
			continue;
		removedNodes[leaf] = true;
		pii parent;
		for(auto i : edges[leaf]){
			if(!removedNodes[i.first])
				parent = i;
		}
		edgeWeight[parent.second] = netNodeChange[leaf]*2;
		neighbourCount[leaf]--;
		neighbourCount[parent.first]--;
		netNodeChange[parent.first] -= netNodeChange[leaf];
		if(neighbourCount[parent.first] == 1){
			leafs.push(parent.first);
		}
		if(neighbourCount[parent.first] == 0){
			removedNodes[parent.first] = true;
		}
	}
	//find the nodes in the last cycle
	vector<int> cycle;
	for(int i = 0;i < n;i++){
		if(!removedNodes[i])
			cycle.push_back(i);
	}
	//if there is no cycle we are finished
	if(cycle.size() == 0){
		for(int i : edgeWeight)
			cout << i << ' ';
		return;
	} else if(cycle.size()%2 == 0){//even cycle is bad
		cout << '0';
		return;
	}

	int curr = cycle[0];
	int next;int nextWeight;
	for(auto i : edges[curr]){
		if(!removedNodes[i.first]){
			next = i.first;
			nextWeight = i.second;
		}
	}
	edgeWeight[nextWeight] += 2*netNodeChange[cycle[0]];
	netNodeChange[next] -= netNodeChange[cycle[0]];
	netNodeChange[cycle[0]] = 0;
	int last = cycle[0];
	curr = next;

	while(curr != cycle[0]){
		pii next1;
		for(auto i : edges[curr]){
			if(!removedNodes[i.first] && i.first != last){
				next1 = i;
			}	
		}
		edgeWeight[next1.second] += 2*netNodeChange[curr];
		netNodeChange[next1.first] -= netNodeChange[curr];
		netNodeChange[curr] = 0;
		last = curr;
		curr = next1.first;
	}

	if(netNodeChange[cycle[0]] % 2 != 0){
		cout << 0;
		return;
	}

	last = next;
	curr = cycle[0];
	int sign = 1;

	bool firstNode = true;
	while(curr != cycle[0] || firstNode){
		pii next1;
		for(auto i : edges[curr]){
			if(!removedNodes[i.first] && i.first != last){
				next1 = i;
			}	
		}
		edgeWeight[next1.second] += netNodeChange[cycle[0]]*sign;
		last = curr;
		curr = next1.first;
		sign = -sign;
		firstNode = false;
	}
	for(int i : edgeWeight)
		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:92:23: warning: 'nextWeight' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |  edgeWeight[nextWeight] += 2*netNodeChange[cycle[0]];
      |                       ^
pipes.cpp:98:13: warning: 'next' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |  while(curr != cycle[0]){

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