Submission #49009

#	Time	Username	Problem	Language	Result	Execution time	Memory
49009		Namnamseo	Pipes (BOI13_pipes)	C++17	100 / 100	146 ms	55080 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define coord_comp(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define v_index(v, x) (lower_bound(all(v),x)-(v).begin())
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T1,typename T2>
void read(pair<T1,T2>& p){ read(p.first); read(p.second); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }

int n,m;
int net[100010];
int net_orig[100010];
vector<pp> edge[100010];
ll ans[100010];
int deg[100010];

bool validate(){
	int cur[n+1];
	for(int i=1; i<=n; ++i) cur[i]=0;
	for(int i=1; i<=n; ++i){
		for(auto& pi:edge[i]){
			cur[i] += ans[pi.second];
		}
		if(cur[i] != net_orig[i]) return false;
	}
	return true;
}

int getOnes(){
	queue<int> ones;
	for(int i=1; i<=n; ++i){
		if(deg[i] == 1u){
			ones.push(i);
		}
	}

	int vises = 0;
	while(ones.size()){
		int x=ones.front(); ones.pop();
		++vises;
		if(deg[x] != 1) continue;
		--deg[x];
		for(auto& pi:edge[x]){
			int y, ei;
			tie(y, ei)=pi;
			if(deg[y] == 0) continue;
			--deg[y];
			if(deg[y] == 1) ones.push(y);
			ans[ei] = net[x];
			net[y] -= net[x];
		}
	}

	return vises;
}

int nxtA[100001];
int nxtB[100001];

int adjS[100001];
int adjP[100001];

int hist[100001];
int nxti[100001];

int main(){
	read(n,m);
	if(m>n){
		puts("0");
		return 0;
	}
	for(int i=1; i<=n; ++i) read(net[i]), net_orig[i]=net[i];
	for(int i=0; i<m; ++i){
		int a,b; read(a,b);
		edge[a].pb({b,i});
		edge[b].pb({a,i});
		++deg[a]; ++deg[b];
	}

	int one_rem = getOnes();
	if(n == one_rem){
		for(int i=0; i<m; ++i) printf("%lld\n", ans[i]*2);
		return 0;
	}

	int sp = -1;
	for(int i=1; i<=n; ++i) if(deg[i]){
		for(auto& pi:edge[i]){
			int y=pi.first;
			if(deg[y]){
				adjS[i] += y;
				adjP[i] = y;
			}
		}
		sp=i;
	}

	vector<int> hist, hii;
	for(int i=sp, j=adjP[sp];;){
		hist.pb(i);
		for(auto& pi : edge[i]) if(pi.first == j){
			hii.pb(pi.second);
		}
		int tmp = i;
		i = j;
		j = adjS[j] - tmp;
		if(i == sp) break;
	}

	if(hist.size() != hii.size()) for(;;);
	int h = hist.size();

	if((n-one_rem) % 2 == 1){
		nxtA[0]=1; nxtB[0]=0;
		for(int i=1; i<h; ++i){
			nxtA[i] = -nxtA[i-1];
			nxtB[i] = net[hist[i]] - nxtB[i-1];
		}
		ll yco = net[hist[0]] - nxtB[h-1];
		int xco = nxtA[h-1]+1;
		ll x = yco/xco;
		for(int i=0; i<h; ++i){
			ans[hii[i]] = nxtA[i]*x + nxtB[i];
		}
		if(!validate()){
			puts("0"); return 0;
		}
		for(int i=0; i<m; ++i) printf("%lld\n", ans[i]*2);
		return 0;
	} else {
		puts("0");	
	}

	return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'void read(int&)':
pipes.cpp:10:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
pipes.cpp: In function 'void read(ll&)':
pipes.cpp:11:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                   ~~~~~^~~~~~~~~~~

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