Submission #1126281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126281		Muhammet	Pipes (BOI13_pipes)	C++20	100 / 100	136 ms	17636 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

#define SZ(s) (int)s.size()

int n, m, nd;

map <pair<int,int>,int> ans;

vector <int> a, u1, u2, deg, vis, v1;

vector <vector <int>> v;

void dfs(int x){
	vis[x] = true;
	v1.push_back(x);
	for(auto i : v[x]){
		if(deg[i] == 2 and !vis[i]){
			dfs(i);
			return;
		}
	}
}

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> m;
	a.resize(n+1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	v.resize(n+1), deg.resize(n+1,0);
	u1.resize(m+1), u2.resize(m+1);
	for(int i = 1; i <= m; i++){
		cin >> u1[i] >> u2[i];
		v[u1[i]].push_back(u2[i]);
		v[u2[i]].push_back(u1[i]);
	}
	if(m > n){
		cout << 0;
		return 0;
	}
	queue <int> q;
	for(int i = 1; i <= n; i++){
		deg[i] = SZ(v[i]);
		if(deg[i] == 1){
			q.push(i);
		}
	}
	while(!q.empty()){
		int ind = q.front();
		q.pop();
		deg[ind]--;
		for(auto i : v[ind]){
			if(deg[i] > 0){
				deg[i]--;
				ans[{min(i,ind), max(i,ind)}] = a[ind];
				a[i] -= a[ind];
				if(deg[i] == 1) q.push(i);
			}
		}
	}
	if(n == m+1){
		for(int i = 1; i <= m; i++){
			cout << 2*ans[{min(u1[i], u2[i]), max(u1[i], u2[i])}] << '\n';
		}
		return 0;
	}
	vis.assign(n+1, 0);
	for(int i = 1; i <= n; i++){
		if(deg[i] == 2){
			nd = i;
			break;
		}
	}
	dfs(nd);
	int n1 = SZ(v1);
	if(n1 % 2 == 0){
		cout << 0;
		return 0;
	}
	int s = 0, s1 = 0;
	for(int i = 0; i < n1; i++){
		s1 += (a[v1[i]] * ((i % 2) ? (-1) : (1)));
	}
	s1 /= 2;
	s += s1;
	// s1 = 0;
	// s -= a[v1[0]];
	for(int i = 1; i < n1; i++){
		s *= (-1);
		s += a[v1[i-1]];
		// int x = (s);
		// x -= s1;
		// cout << s << ' ' << s1 << "\n";
		ans[{min(v1[i-1], v1[i]), max(v1[i-1], v1[i])}] = s;
	}
	s *= (-1);
	s += (a[v1[n1-1]]);
	// cout << s << ' ' << s1 << "\n";
	// int x = (s);
	// x -= s1;
	ans[{min(v1[n1-1], v1[0]), max(v1[n1-1], v1[0])}] = s;
	for(int i = 1; i <= m; i++){
		cout << 2*ans[{min(u1[i], u2[i]), max(u1[i], u2[i])}] << '\n';
	}
}

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