답안 #114776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114776	2019-06-02T16:18:31 Z	luciocf	Pipes (BOI13_pipes)	C++14	74.0741 / 100	260 ms	17176 KB

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], nivel[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;

			if (nivel[firstCycle] > nivel[lastCycle])
				swap(firstCycle, lastCycle);

			continue;
		}

		pai[v] = u, nivel[v] = nivel[u]+1, 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)
{
	if (firstCycle == -1) return;

	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 (v != firstCycle)
	{
		int e = edgePai[v];

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

		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

pipes.cpp: In function 'int main()':
pipes.cpp:122: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:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c[i]);
   ~~~~~^~~~~~~~~~~~~
pipes.cpp:130: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	4 ms	2816 KB	Output is correct
2	Correct	4 ms	2816 KB	Output is correct
3	Correct	5 ms	2816 KB	Output is correct
4	Correct	94 ms	9312 KB	Output is correct
5	Correct	3 ms	2816 KB	Output is correct
6	Correct	4 ms	2816 KB	Output is correct
7	Correct	4 ms	2816 KB	Output is correct
8	Correct	4 ms	2816 KB	Output is correct
9	Correct	5 ms	2816 KB	Output is correct
10	Correct	5 ms	2816 KB	Output is correct
11	Correct	5 ms	2816 KB	Output is correct
12	Correct	5 ms	2816 KB	Output is correct
13	Correct	66 ms	7928 KB	Output is correct
14	Correct	89 ms	8872 KB	Output is correct
15	Correct	97 ms	9204 KB	Output is correct
16	Correct	70 ms	8312 KB	Output is correct
17	Correct	90 ms	9212 KB	Output is correct
18	Correct	96 ms	9276 KB	Output is correct
19	Correct	116 ms	11000 KB	Output is correct
20	Correct	4 ms	2816 KB	Output is correct
21	Correct	5 ms	2816 KB	Output is correct
22	Correct	86 ms	9208 KB	Output is correct
23	Correct	64 ms	7928 KB	Output is correct
24	Correct	87 ms	9336 KB	Output is correct
25	Correct	70 ms	8184 KB	Output is correct

Subtask #2

44.0740740741 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	2816 KB	Output isn't correct
2	Incorrect	4 ms	2944 KB	Output isn't correct
3	Correct	69 ms	9996 KB	Output is correct
4	Correct	59 ms	6648 KB	Output is correct
5	Correct	70 ms	6828 KB	Output is correct
6	Correct	254 ms	17176 KB	Output is correct
7	Incorrect	4 ms	2816 KB	Output isn't correct
8	Incorrect	4 ms	2816 KB	Output isn't correct
9	Correct	4 ms	2688 KB	Output is correct
10	Correct	3 ms	2688 KB	Output is correct
11	Correct	3 ms	2688 KB	Output is correct
12	Correct	4 ms	2688 KB	Output is correct
13	Correct	4 ms	2688 KB	Output is correct
14	Incorrect	4 ms	2816 KB	Output isn't correct
15	Incorrect	1 ms	2944 KB	Output isn't correct
16	Incorrect	4 ms	2816 KB	Output isn't correct
17	Correct	4 ms	2816 KB	Output is correct
18	Correct	4 ms	2688 KB	Output is correct
19	Correct	4 ms	2688 KB	Output is correct
20	Correct	4 ms	2688 KB	Output is correct
21	Correct	5 ms	2816 KB	Output is correct
22	Incorrect	5 ms	2944 KB	Output isn't correct
23	Incorrect	95 ms	10304 KB	Output isn't correct
24	Incorrect	107 ms	11432 KB	Output isn't correct
25	Correct	70 ms	9980 KB	Output is correct
26	Correct	60 ms	6648 KB	Output is correct
27	Correct	68 ms	6520 KB	Output is correct
28	Correct	65 ms	6904 KB	Output is correct
29	Correct	222 ms	14584 KB	Output is correct
30	Incorrect	112 ms	12664 KB	Output isn't correct
31	Incorrect	112 ms	12792 KB	Output isn't correct
32	Incorrect	85 ms	9976 KB	Output isn't correct
33	Correct	90 ms	10660 KB	Output is correct
34	Correct	56 ms	6520 KB	Output is correct
35	Correct	55 ms	6520 KB	Output is correct
36	Correct	59 ms	7032 KB	Output is correct
37	Correct	260 ms	17148 KB	Output is correct
38	Incorrect	121 ms	12320 KB	Output isn't correct
39	Incorrect	89 ms	9720 KB	Output isn't correct
40	Incorrect	120 ms	11384 KB	Output isn't correct
41	Correct	83 ms	12024 KB	Output is correct
42	Correct	56 ms	6392 KB	Output is correct
43	Correct	58 ms	6520 KB	Output is correct
44	Correct	56 ms	6776 KB	Output is correct
45	Correct	182 ms	15352 KB	Output is correct
46	Incorrect	134 ms	13304 KB	Output isn't correct
47	Incorrect	113 ms	11384 KB	Output isn't correct
48	Incorrect	136 ms	12760 KB	Output isn't correct
49	Correct	80 ms	8824 KB	Output is correct
50	Correct	65 ms	6648 KB	Output is correct
51	Correct	63 ms	6776 KB	Output is correct
52	Correct	60 ms	6524 KB	Output is correct
53	Correct	249 ms	15264 KB	Output is correct
54	Incorrect	129 ms	11896 KB	Output isn't correct