oj.uz

답안 #106158

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106158 2019-04-16T22:51:52 Z luciocf Pipes (BOI13_pipes) C++14
74.0741 / 100
 344 ms 38264 KB 
#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

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4736 KB Output is correct
2 Correct 5 ms 4736 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 147 ms 34936 KB Output is correct
5 Correct 5 ms 4736 KB Output is correct
6 Correct 5 ms 4736 KB Output is correct
7 Correct 6 ms 4736 KB Output is correct
8 Correct 6 ms 4784 KB Output is correct
9 Correct 8 ms 4992 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct
11 Correct 7 ms 4992 KB Output is correct
12 Correct 7 ms 4992 KB Output is correct
13 Correct 120 ms 28920 KB Output is correct
14 Correct 121 ms 33400 KB Output is correct
15 Correct 180 ms 35192 KB Output is correct
16 Correct 291 ms 30576 KB Output is correct
17 Correct 236 ms 35020 KB Output is correct
18 Correct 173 ms 35192 KB Output is correct
19 Correct 222 ms 36940 KB Output is correct
20 Correct 16 ms 4608 KB Output is correct
21 Correct 7 ms 4992 KB Output is correct
22 Correct 170 ms 35200 KB Output is correct
23 Correct 127 ms 28792 KB Output is correct
24 Correct 191 ms 35164 KB Output is correct
25 Correct 169 ms 30072 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 4608 KB Output isn't correct
2 Incorrect 6 ms 4736 KB Output isn't correct
3 Correct 186 ms 34884 KB Output is correct
4 Correct 107 ms 14396 KB Output is correct
5 Correct 116 ms 11072 KB Output is correct
6 Correct 344 ms 28456 KB Output is correct
7 Incorrect 7 ms 4736 KB Output isn't correct
8 Incorrect 6 ms 4736 KB Output isn't correct
9 Correct 6 ms 4736 KB Output is correct
10 Correct 6 ms 4608 KB Output is correct
11 Correct 6 ms 4736 KB Output is correct
12 Correct 6 ms 4736 KB Output is correct
13 Correct 6 ms 4736 KB Output is correct
14 Incorrect 6 ms 4736 KB Output isn't correct
15 Incorrect 6 ms 4736 KB Output isn't correct
16 Incorrect 6 ms 4736 KB Output isn't correct
17 Correct 6 ms 4992 KB Output is correct
18 Correct 6 ms 4736 KB Output is correct
19 Correct 6 ms 4736 KB Output is correct
20 Correct 6 ms 4736 KB Output is correct
21 Correct 7 ms 4864 KB Output is correct
22 Incorrect 6 ms 4736 KB Output isn't correct
23 Incorrect 85 ms 12228 KB Output isn't correct
24 Incorrect 92 ms 13432 KB Output isn't correct
25 Correct 198 ms 34888 KB Output is correct
26 Correct 141 ms 13816 KB Output is correct
27 Correct 107 ms 14048 KB Output is correct
28 Correct 140 ms 11188 KB Output is correct
29 Correct 288 ms 24796 KB Output is correct
30 Incorrect 108 ms 14712 KB Output isn't correct
31 Incorrect 100 ms 14840 KB Output isn't correct
32 Incorrect 103 ms 11900 KB Output isn't correct
33 Correct 199 ms 36908 KB Output is correct
34 Correct 103 ms 13480 KB Output is correct
35 Correct 107 ms 14328 KB Output is correct
36 Correct 100 ms 11196 KB Output is correct
37 Correct 335 ms 28448 KB Output is correct
38 Incorrect 94 ms 14456 KB Output isn't correct
39 Incorrect 108 ms 11676 KB Output isn't correct
40 Incorrect 100 ms 13176 KB Output isn't correct
41 Correct 175 ms 38264 KB Output is correct
42 Correct 88 ms 13560 KB Output is correct
43 Correct 99 ms 14492 KB Output is correct
44 Correct 79 ms 11128 KB Output is correct
45 Correct 238 ms 23700 KB Output is correct
46 Incorrect 141 ms 15096 KB Output isn't correct
47 Incorrect 111 ms 13204 KB Output isn't correct
48 Incorrect 113 ms 14636 KB Output isn't correct
49 Correct 182 ms 33548 KB Output is correct
50 Correct 102 ms 13432 KB Output is correct
51 Correct 93 ms 12456 KB Output is correct
52 Correct 130 ms 11896 KB Output is correct
53 Correct 275 ms 24440 KB Output is correct
54 Incorrect 103 ms 13916 KB Output isn't correct