Submission #518905

#	Time	Username	Problem	Language	Result	Execution time	Memory
518905		blue	Pipes (BOI13_pipes)	C++17	90.93 / 100	171 ms	24128 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]]

		x = (c[nodelist[0]] - b[0] - b[Z-1]) / 2;

		for(int y = 0; y < Z; y++)
			ans[ edgelist[y] ] = 2 * (a[y] * x  +  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:60:6: warning: unused variable 'endv' [-Wunused-variable]
   60 |  int endv = -1;
      |      ^~~~

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