Submission #106158

#	Time	Username	Problem	Language	Result	Execution time	Memory
106158		luciocf	Pipes (BOI13_pipes)	C++14	74.07 / 100	344 ms	38264 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int maxm = 5e5+10;
const int maxl = 20;
const int inf = 2e9+10;

struct T
{
	int x, mx, mi;
} tab[maxn][maxl];

typedef pair<int, int> pii;

int a[maxn], cur[maxn];
pii E[maxm];

int edge[maxn], costEdge[maxm];

int pai[maxn], nivel[maxn];

bool mark[maxn];

vector<pii> grafo[maxn];

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

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

		edge[v] = e;
		pai[v] = u, nivel[v] = nivel[u]+1;

		dfs(v, u);

		cur[u] += costEdge[e]/2;
	}

	if (u != 1)
	{
		costEdge[edge[u]] = 2*(a[u]-cur[u]);
		cur[u] = a[u];
	}
}

void build(int n)
{
	for (int i = 1; i <= n; i++)
	{
		tab[i][0].x = pai[i];
		tab[i][0].mx = tab[i][0].mi = costEdge[edge[i]];
	}

	for (int j = 1; j < maxl; j++)
	{
		for (int i = 1; i <= n; i++)
		{
			tab[i][j].x = tab[tab[i][j-1].x][j-1].x;
			tab[i][j].mx = max(tab[i][j-1].mx, tab[tab[i][j-1].x][j-1].mx);
			tab[i][j].mi = max(tab[i][j-1].mi, tab[tab[i][j-1].x][j-1].mi);
		}
	}
}

int lca(int u, int v)
{
	if (nivel[u] < nivel[v]) swap(u, v);

	for (int i = maxl-1; i >= 0; i--)
		if (nivel[u]-(1<<i) >= nivel[v])
			u = tab[u][i].x;

	if (u == v) return u;

	for (int i = maxl-1; i >= 0; i--)
		if (tab[u][i].x && tab[v][i].x && tab[u][i].x != tab[v][i].x)
			u = tab[u][i].x, v = tab[v][i].x;

	return pai[u];
}

pii get(int u, int l)
{
	int mx = -inf, mi = inf;

	for (int i = maxl-1; i >= 0; i--)
	{
		if (nivel[u]-(1<<i) >= nivel[l])
		{
			mx = max(mx, tab[u][i].mx);
			mi = min(mi, tab[u][i].mi);
			u = tab[u][i].x;
		}
	}

	return {mx, mi};
}

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

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[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});

		E[i] = {u, v};
	}

	memset(costEdge, -1, sizeof costEdge);

	dfs(1, 0);

	if (cur[1] != a[1])
	{
		printf("0\n");
		return 0;
	}

	build(n);

	bool ok = 1;

	for (int i = 1; i <= m; i++)
	{
		if (costEdge[i] == -1)
		{
			int u = E[i].first, v = E[i].second;

			int low = lca(u, v), mx = -inf, mi = inf;

			pii ans = get(u, low);
			mx = max(mx, ans.first); mi = min(mi, ans.second);

			ans = get(v, low);
			mx = max(mx, ans.first); mi = min(mi, ans.second);

			if (mx != 0 || mi != 0)
			{
				ok = 0;
				break;
			}
		}
	}

	if (!ok) printf("0\n");
	else
	{
		for (int i = 1; i <= m; i++)
		{
			if (costEdge[i] == -1) printf("0\n");
			else printf("%d\n", costEdge[i]);
		}
	}
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:108: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:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
pipes.cpp:116: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: 44.074074074074076 / 70