oj.uz

답안 #106160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106160 2019-04-16T23:01:29 Z luciocf Pipes (BOI13_pipes) C++14
74.0741 / 100
 361 ms 38308 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 = min(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 6 ms 4736 KB Output is correct
2 Correct 6 ms 4736 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 199 ms 35092 KB Output is correct
5 Correct 5 ms 4608 KB Output is correct
6 Correct 5 ms 4736 KB Output is correct
7 Correct 6 ms 4736 KB Output is correct
8 Correct 7 ms 4736 KB Output is correct
9 Correct 7 ms 4992 KB Output is correct
10 Correct 6 ms 4992 KB Output is correct
11 Correct 8 ms 4992 KB Output is correct
12 Correct 8 ms 4992 KB Output is correct
13 Correct 125 ms 28892 KB Output is correct
14 Correct 167 ms 33412 KB Output is correct
15 Correct 202 ms 35196 KB Output is correct
16 Correct 138 ms 30556 KB Output is correct
17 Correct 201 ms 35116 KB Output is correct
18 Correct 176 ms 35200 KB Output is correct
19 Correct 177 ms 36856 KB Output is correct
20 Correct 6 ms 4736 KB Output is correct
21 Correct 6 ms 4992 KB Output is correct
22 Correct 235 ms 35192 KB Output is correct
23 Correct 125 ms 28792 KB Output is correct
24 Correct 163 ms 35172 KB Output is correct
25 Correct 122 ms 30080 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 4708 KB Output isn't correct
2 Incorrect 5 ms 4736 KB Output isn't correct
3 Correct 125 ms 34808 KB Output is correct
4 Correct 99 ms 14200 KB Output is correct
5 Correct 99 ms 11000 KB Output is correct
6 Correct 361 ms 28436 KB Output is correct
7 Incorrect 6 ms 4660 KB Output isn't correct
8 Incorrect 5 ms 4736 KB Output isn't correct
9 Correct 6 ms 4864 KB Output is correct
10 Correct 6 ms 4736 KB Output is correct
11 Correct 7 ms 4608 KB Output is correct
12 Correct 6 ms 4736 KB Output is correct
13 Correct 5 ms 4608 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 7 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 7 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 76 ms 12152 KB Output isn't correct
24 Incorrect 116 ms 13304 KB Output isn't correct
25 Correct 167 ms 34864 KB Output is correct
26 Correct 104 ms 13900 KB Output is correct
27 Correct 106 ms 14072 KB Output is correct
28 Correct 147 ms 11232 KB Output is correct
29 Correct 293 ms 24952 KB Output is correct
30 Incorrect 108 ms 14712 KB Output isn't correct
31 Incorrect 109 ms 14712 KB Output isn't correct
32 Incorrect 91 ms 11896 KB Output isn't correct
33 Correct 247 ms 36984 KB Output is correct
34 Correct 107 ms 13432 KB Output is correct
35 Correct 100 ms 14328 KB Output is correct
36 Correct 102 ms 11128 KB Output is correct
37 Correct 332 ms 28440 KB Output is correct
38 Incorrect 104 ms 14328 KB Output isn't correct
39 Incorrect 84 ms 11640 KB Output isn't correct
40 Incorrect 115 ms 13304 KB Output isn't correct
41 Correct 189 ms 38308 KB Output is correct
42 Correct 99 ms 13732 KB Output is correct
43 Correct 90 ms 14584 KB Output is correct
44 Correct 87 ms 11000 KB Output is correct
45 Correct 239 ms 23644 KB Output is correct
46 Incorrect 100 ms 15096 KB Output isn't correct
47 Incorrect 103 ms 13160 KB Output isn't correct
48 Incorrect 136 ms 14712 KB Output isn't correct
49 Correct 145 ms 33572 KB Output is correct
50 Correct 89 ms 13560 KB Output is correct
51 Correct 88 ms 12408 KB Output is correct
52 Correct 96 ms 11896 KB Output is correct
53 Correct 256 ms 24540 KB Output is correct
54 Incorrect 91 ms 13816 KB Output isn't correct