Submission #114768

#	Time	Username	Problem	Language	Result	Execution time	Memory
114768		luciocf	Pipes (BOI13_pipes)	C++14	65 / 100	1090 ms	23160 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

typedef long long ll;
typedef pair<int, int> pii;

int n, m;

int c[maxn];

int ans[maxn];

int pai[maxn], edgePai[maxn];

int firstCycle=-1, lastCycle=-1, lastEdge = -1;

bool mark[maxn], inCycle[maxn];

vector<pii> grafo[maxn];

void dfs(int u, int p)
{
	mark[u] = true;

	for (auto pp: grafo[u])
	{
		int v = pp.first, e = pp.second;

		if (mark[v])
		{
			if (v == p) continue;

			firstCycle = v, lastCycle = u, lastEdge = e;
			continue;
		}

		pai[v] = u, edgePai[v] = e;
		dfs(v, u);
	}
}

bool checkSize(void)
{
	if (firstCycle == -1) return 1;

	int v = lastCycle, qtd = 0;

	while (true)
	{
		inCycle[v] = true;
		qtd++;

		if (v == firstCycle) break;

		v = pai[v];
	}

	return (qtd%2 == 1);
}

void solve(int u)
{
	mark[u] = true;

	for (auto pp: grafo[u])
	{
		int v = pp.first, e = pp.second;

		if (mark[v]) continue;

		solve(v);

		if (!inCycle[v])
		{
			ans[e] = 2*c[v];
			c[u] -= ans[e]/2;
		}
	}
}

void solveCycle(void)
{
	int v = lastCycle, sign = 1;
	ll sum = 0ll;

	while (true)
	{
		sum += 1ll*sign*c[v];

		if (v == firstCycle) break;

		sign *= -1, v = pai[v];
	}

	ans[lastEdge] = 2ll*c[firstCycle] - sum;

	int prev = ans[lastEdge];
	v = lastCycle;

	while (true)
	{
		int e = edgePai[v];

		ans[e] = 2*c[v] - prev;

		if (v == firstCycle) break;

		v = pai[v];
	}
}

int main(void)
{
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
		scanf("%d", &c[i]);

	for (int i = 1; i <= m; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);

		grafo[u].push_back({v, i});
		grafo[v].push_back({u, i});
	}

	if (m > n)
	{
		printf("0\n");
		return 0;
	}

	dfs(1, 0);

	if (!checkSize())
	{
		printf("0\n");
		return 0;
	}

	memset(mark, 0, sizeof mark);
	solve(1);

	solveCycle();

	for (int i = 1; i <= m; i++)
		printf("%d\n", ans[i]);
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c[i]);
   ~~~~~^~~~~~~~~~~~~
pipes.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

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