Submission #555898

#	Time	Username	Problem	Language	Result	Execution time	Memory
555898		blue	Pipes (BOI13_pipes)	C++17	90.93 / 100	192 ms	29704 KiB

pipes

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = vector<pl>;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define sz(x) int(x.size())
 
const int mx = 100'000;
const int emx = 500'000;
 
vl c(1+mx);
vector<pii> edge[1+mx];
 
vi deg(1+mx, 0);
vi visit(1+emx, 0);
 
vector<ll> ans(1+emx);
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int N, M;
	cin >> N >> M;
 
	for(int i = 1; i <= N; i++) cin >> c[i];
 
	for(int j = 1; j <= M; j++)
	{
		int u, v;
		cin >> u >> v;
		edge[u].push_back({v, j});
		edge[v].push_back({u, j});
		deg[u]++;
		deg[v]++;
	}
 
	if(M > N)
	{
		cout << "0\n";
		return 0;
	}
 
	queue<int> tbv;
	for(int i = 1; i <= N; i++)
	{
		if(deg[i] == 1)
		{
			tbv.push(i);
		}
	}
 
	int endv = -1;
 
	vi node_visit(1+N, 0);
 
	while(!tbv.empty())
	{
		int u = tbv.front();
		tbv.pop();
 
		node_visit[u] = 1;
 
		// cerr << "u = " << u << '\n';
 
		int elim = 0;
 
		for(auto ed: edge[u])
		{
			int v = ed.first;
 
			if(visit[ed.second]) continue;
 
			visit[ed.second] = 1;
 
			deg[v]--;
 
			elim = 1;
 
			if(deg[v] <= 1)
			{
				tbv.push(v);
			}
			ans[ed.second] = 2*c[u];
			// cerr << ed.first << ' ' << ed.second << " : " << 2*c[u] << '\n';
 
			c[v] -= c[u];
			c[u] -= c[u];
 
		}
 
		if(!elim)
		{
			if(M == N-1)
			{
				if(c[u] != 0)
				{
					cout << "0\n";
					return 0;
				}
			}
		}
	}
 
	// for(int u = 1; u <= N; u++)
	// {
	// 	cerr << "node = " << u << '\n';
	// 	for(auto ed: edge[u]) cerr << ed.first << ' ' << ed.second << '\n';
	// }
 
 
	if(M == N)
	{
		// cerr << "done\n";
		ll a[1+N], b[1+N];
 
		int u = 1;
		while(node_visit[u]) u++;
 
		int src = u;
 
		vi edgelist;
		vi nodelist;
 
		while(1)
		{
			int nv = 0;
			for(auto ed: edge[u])
			{
				if(visit[ed.second]) continue;
				visit[ed.second] = 1;
				nv = 1;
 
				nodelist.push_back(u);
				edgelist.push_back(ed.second);
 
				// cerr << u << " -> " << ed.first << ' ' << ed.second << '\n';
 
				u = ed.first;
				break;
			}
			if(!nv) break;
		}
 
		int Z = sz(edgelist);
 
		a[0] = 1;
		b[0] = 0;
 
		if(Z % 2 == 0)
		{
			cout << "0\n";
			return 0;
		}
 
		for(int z = 0; z+1 < Z; z++)
		{
			a[z+1] = -a[z];
			b[z+1] = c[ nodelist[z+1] ] - b[z];
		}
 
 
		// for(int i = 0; i < Z; i++) cerr << nodelist[i] << ' ' << edgelist[i] << ' ' << a[i] << ' ' << b[i] << '\n';
 
		ll x = 0;
 
		//if(b[0] + b[z-1] != c[ nodelist[] ])
		if((b[0] + b[Z-1]) % 2 != c[nodelist[0]] % 2) 
		{
			cout << "0\n";
		}
 
		//x + b[0]  +  x + b[z-1]  ==  c[nodelist[0]]
 
		ll x2 = (c[nodelist[0]] - b[0] - b[Z-1]);
 
		for(int y = 0; y < Z; y++)
			ans[ edgelist[y] ] = (a[y] * x2  +  2*b[y]);
	}
 
 
 
 
	for(int e = 1; e <= M; e++)
	{
		cout << ans[e] << '\n';
	}
 
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:127:7: warning: unused variable 'src' [-Wunused-variable]
  127 |   int src = u;
      |       ^~~
pipes.cpp:172:6: warning: unused variable 'x' [-Wunused-variable]
  172 |   ll x = 0;
      |      ^
pipes.cpp:60:6: warning: unused variable 'endv' [-Wunused-variable]
   60 |  int endv = -1;
      |      ^~~~

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