Submission #518895

#	Time	Username	Problem	Language	Result	Execution time	Memory
518895		blue	Pipes (BOI13_pipes)	C++17	55.40 / 100	1065 ms	29764 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>;

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;

	while(!tbv.empty())
	{
		int u = tbv.front();
		tbv.pop();

		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 e = 1; e <= M; e++)
	{
		cout << ans[e] << '\n';
	}

}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:59:6: warning: unused variable 'endv' [-Wunused-variable]
   59 |  int endv = -1;
      |      ^~~~

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