Submission #121562

#	Time	Username	Problem	Language	Result	Execution time	Memory
121562		Adhyyan1252	Pipes (BOI13_pipes)	C++11	100 / 100	151 ms	20588 KiB

pipes

#include<bits/stdc++.h>

using namespace std;

#define int long long

struct edge{
	int u, v;
	int val = LONG_LONG_MAX;
};

vector<edge> e;
vector<vector<int> > g;
vector<int> s;
vector<int> st, cycle;
vector<int> cf;
vector<int> c;
int tym = 1;
bool dfs(int cur, int par){
	s[cur] = tym;
	tym++;
	st.push_back(cur);
	for(int u: g[cur]){
		int next = e[u].u + e[u].v - cur;
		if(s[next] == 0){ //child
			if(dfs(next, cur)) return true;
		}else if(next != par){ //back edge
			while(st.back() != next){
				cycle.push_back(st.back());
				st.pop_back();
			}
			cycle.push_back(st.back());
			st.pop_back();
			return true;
		}
	}
	st.pop_back();
	return false;
}

int find(int cur, int parid){
	int sum = 0;
	for(int eid: g[cur]){
		int next = e[eid].u + e[eid].v - cur;
		if(cf[next]) continue;
		if(eid == parid) continue;
		sum += find(next, eid);
	}
	if(parid == -1) return sum;
	e[parid].val = c[cur] - sum;
	return e[parid].val;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int n, m; cin>>n>>m;
	if(m > n){
		cout<<0<<endl;
		return 0;
	}
	c.resize(n);
	for(int i = 0; i < n; i++){
		cin>>c[i]; 
	}
	g.resize(n);
	e.resize(m);
	for(int i = 0; i < m; i++){
		int u, v; cin>>u>>v; u--, v--;
		g[u].push_back(i);
		g[v].push_back(i);
		e[i].u = u;
		e[i].v = v;
	}
	
	s.resize(n);
	cf.resize(n);
	dfs(0, -1);
	//cout<<"REACHED "<<cycle.size()<<endl;
	for(int u: cycle){
		cf[u] = true;
		//cout<<"C: "<<u<<endl;
	}
	if(cycle.size() == 0){
		//its a tree, just dfs from anywhere
		find(0, -1);
	}else if(cycle.size()%2 == 0){
		cout<<0<<endl;
		return 0;
	}else{
		vector<int> off(n);
		int sum = 0;
		int cnt = 1;
		for(int u: cycle){
			off[u] = find(u, -1);
			//cout<<"OFF "<<u<<" "<<off[u]<<" "<<(c[u]-off[u])*cnt<<" "<<cnt<<endl;
			sum += (c[u] - off[u])*(cnt);
			cnt *= -1;
		}
		sum /= 2;
		//cout<<"SUM "<<sum<<endl;
		int id = -1, prev = sum;
		//sum is the value of edge between u and u+1
		for(int i = 0; i < cycle.size(); i++){
			id = -1;
			int u = cycle[i];
			for(int eid: g[u]){
				int next = e[eid].u + e[eid].v - u;
				if(next == cycle[(i+1)%cycle.size()]){
					//found the egde
					id = eid;
					break;
				}
			}
			assert(id != -1);
			e[id].val = c[u] - off[u] - prev;
			prev = e[id].val;
		}
	}
	for(int i = 0; i < e.size(); i++){
		assert(e[i].val != LONG_LONG_MAX);
		cout<<e[i].val*2<<"\n";
	}
	cout.flush();
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < cycle.size(); i++){
                  ~~^~~~~~~~~~~~~~
pipes.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < e.size(); i++){
                 ~~^~~~~~~~~~

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