Submission #483572

#	Time	Username	Problem	Language	Result	Execution time	Memory
483572		robell	Pipes (BOI13_pipes)	C++14	65 / 100	161 ms	17208 KiB

pipes

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
#define pb push_back
#define eb emplace_back
#define countbits __builtin_popcount
#define beg0 __builtin_clz
#define terminal0 __builtin_ctz
#define f first
#define s second
int mod=1e9+7;
void setIO(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
}
void setIO(string f){
	freopen((f+".in").c_str(),"r",stdin);
	freopen((f+".out").c_str(),"w",stdout);
	setIO();
}
ll N, M,pump[(int)5e5],c[(int)1e5],change[(int)1e5];
int start = 0;
vector<pair<int,int>> l[(int)1e5];
vector<int> fcyc;
bool cyc = false,v[(int)1e5],oncyc[(int)1e5];
void dfs2(int ind, int p){
	if (cyc) return;
	v[ind]=true;
	for (pair<int,int> j:l[ind]){
		if (cyc) break;
		if (j.first==p) continue;
		if (v[j.first]){cyc=true;return;}
		else{
			dfs2(j.first,ind);
		}
	}
}
ll dfs(int ind, int p){
	v[ind]=true;
	ll val = c[ind];
	for (pair<int,int> j:l[ind]){
		if (j.first==p) continue;
		pump[j.second]=dfs(j.first,ind);
		val-=pump[j.second];
	}
	return val;
}
void findcyc(int ind){
	v[ind]=true;
	fcyc.pb(ind);
	for (pair<int,int> e:l[ind]){
		if (!v[e.first]){
			findcyc(e.first);
		}else if (!oncyc[e.first]&& fcyc.size()>=2 && fcyc[fcyc.size()-2]!=ind){
			for (int i=fcyc.size()-1;fcyc[i]!=e.f;i--){
				oncyc[fcyc[i]]=true;
			}
			oncyc[e.f]=true;
		}
	}
	fcyc.pop_back();
}
void prefix(int x,int p,int p0){
	for(auto v:l[x]){
		if(!oncyc[v.f] || v.f==p || v.f==p0)
			continue;
		change[v.f]=c[v.f]-change[x];
		prefix(v.f,x,p0);
		return;
	}
	start=change[x];
	return;
}
void solve_trees(int x,int p){
	for(auto v:l[x]){
		if(oncyc[v.f] || v.f==p)
			continue;
		solve_trees(v.f,x);
		pump[v.s]=2*c[v.f];
		c[x]-=c[v.f];
	}
	return;
}
void solvec(int x,int p,int p0,bool sgn_x){
	for(auto v:l[x]){
		if(!oncyc[v.f] || v.f==p)continue;
		if(v.f==p0){pump[v.s]=start;return;}
		if(sgn_x) pump[v.s]=-start+2*change[x];
		else pump[v.s]=start+2*change[x];
		solvec(v.f,x,p0,!sgn_x);
		return;
	}
	return;
}
int main(){
	setIO(); cin >> N >> M;
	for (int i=0;i<N;i++) cin >> c[i];
	for (int i=0;i<M;i++){
		int u,v; cin >> u >> v;
		l[--u].pb({--v,i});
		l[v].pb({u,i});
	}
	if (M>N){cout << "0\n";return 0;}
	if (M<N){
		for (int i=0;i<N;i++){
			if (!v[i]) dfs2(i,i);
		}
		memset(v,0,sizeof(v));
		for (int i=0;i<N;i++){
			if (!v[i]) dfs(i,i);
		}
		for (int i=0;i<M;i++){
			cout << 2*pump[i] << "\n";
		}
	}else{
		findcyc(0);
		int countc=0,start=0;
		for (int i=0;i<N;i++){
			if (oncyc[i]){
				solve_trees(i,0);
				countc++;
				start=i;
			}
		}
		if (countc%2==0){
			cout << "0\n";
		}
		change[start]=c[start];
		prefix(start,0,start);
		solvec(start,0,start,1);
		for (int i=0;i<M;i++){
			cout << pump[i] << " ";
		}
	}
}

Compilation message (stderr)

pipes.cpp: In function 'void setIO(std::string)':
pipes.cpp:21:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  freopen((f+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:22:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  freopen((f+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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