oj.uz

답안 #106159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
106159 2019-04-16T22:53:52 Z luciocf Pipes (BOI13_pipes) C++14
74.0741 / 100
 356 ms 38392 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 init(int n)
{
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < maxl; j++)
			tab[i][j].mx = -inf, tab[i][j].mi = inf;
}

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;
	}

	init(n);
	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:115: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:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
pipes.cpp:123: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 7 ms 4992 KB Output is correct
4 Correct 155 ms 34920 KB Output is correct
5 Correct 6 ms 4736 KB Output is correct
6 Correct 5 ms 4736 KB Output is correct
7 Correct 7 ms 4736 KB Output is correct
8 Correct 6 ms 4736 KB Output is correct
9 Correct 8 ms 4992 KB Output is correct
10 Correct 7 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 109 ms 28796 KB Output is correct
14 Correct 141 ms 33400 KB Output is correct
15 Correct 189 ms 35192 KB Output is correct
16 Correct 153 ms 30608 KB Output is correct
17 Correct 151 ms 35064 KB Output is correct
18 Correct 183 ms 35140 KB Output is correct
19 Correct 217 ms 36984 KB Output is correct
20 Correct 5 ms 4736 KB Output is correct
21 Correct 6 ms 4992 KB Output is correct
22 Correct 152 ms 35196 KB Output is correct
23 Correct 111 ms 28924 KB Output is correct
24 Correct 145 ms 35192 KB Output is correct
25 Correct 133 ms 30076 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 4608 KB Output isn't correct
2 Incorrect 8 ms 4736 KB Output isn't correct
3 Correct 244 ms 34852 KB Output is correct
4 Correct 101 ms 14328 KB Output is correct
5 Correct 101 ms 10976 KB Output is correct
6 Correct 352 ms 28344 KB Output is correct
7 Incorrect 5 ms 4608 KB Output isn't correct
8 Incorrect 5 ms 4608 KB Output isn't correct
9 Correct 5 ms 4736 KB Output is correct
10 Correct 7 ms 4736 KB Output is correct
11 Correct 5 ms 4608 KB Output is correct
12 Correct 6 ms 4608 KB Output is correct
13 Correct 6 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 8 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 8 ms 4736 KB Output isn't correct
23 Incorrect 91 ms 12140 KB Output isn't correct
24 Incorrect 118 ms 13364 KB Output isn't correct
25 Correct 191 ms 34936 KB Output is correct
26 Correct 97 ms 13944 KB Output is correct
27 Correct 104 ms 14072 KB Output is correct
28 Correct 111 ms 11176 KB Output is correct
29 Correct 298 ms 25080 KB Output is correct
30 Incorrect 99 ms 14712 KB Output isn't correct
31 Incorrect 110 ms 14712 KB Output isn't correct
32 Incorrect 107 ms 11908 KB Output isn't correct
33 Correct 183 ms 36968 KB Output is correct
34 Correct 93 ms 13404 KB Output is correct
35 Correct 97 ms 14348 KB Output is correct
36 Correct 84 ms 11000 KB Output is correct
37 Correct 356 ms 28416 KB Output is correct
38 Incorrect 93 ms 14200 KB Output isn't correct
39 Incorrect 98 ms 11644 KB Output isn't correct
40 Incorrect 95 ms 13276 KB Output isn't correct
41 Correct 205 ms 38392 KB Output is correct
42 Correct 99 ms 13560 KB Output is correct
43 Correct 107 ms 14516 KB Output is correct
44 Correct 95 ms 11000 KB Output is correct
45 Correct 262 ms 23756 KB Output is correct
46 Incorrect 105 ms 15096 KB Output isn't correct
47 Incorrect 104 ms 13272 KB Output isn't correct
48 Incorrect 112 ms 14576 KB Output isn't correct
49 Correct 163 ms 33576 KB Output is correct
50 Correct 89 ms 13488 KB Output is correct
51 Correct 98 ms 12548 KB Output is correct
52 Correct 89 ms 11896 KB Output is correct
53 Correct 262 ms 24496 KB Output is correct
54 Incorrect 89 ms 13816 KB Output isn't correct