답안 #110780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
110780 2019-05-12T08:16:26 Z ckodser Pipes (BOI13_pipes) C++14
44.0741 / 100
182 ms 14708 KB
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 100005;
int n, m, cv, cu, A[N], B[N], M[N], P[N], R[N];
ll C[N], D[N];
vector < int > Adj[N];
void DFSC(int v, int p)
{
	M[v] = 1;
	for (int id : Adj[v])
		if (id != p)
		{
			int u = A[id] ^ B[id] ^ v;
			if (M[u])
				cv = v, cu = u;
			if (!M[u])
				P[u] = v, DFSC(u, id);
		}
}
void DFS(int v, int p)
{
	for (int id : Adj[v])
		if (id != p)
			DFS(A[id] ^ B[id] ^ v, id);
	int par = A[p] ^ B[p] ^ v;
	D[p] += C[v] + C[v];
	C[par] -= C[v];
	C[v] = 0;
}
void DFS2(int v, int p)
{
	M[v] = 2;
	P[v] = p;
	R[v] = Adj[v][0] ^ Adj[v][1] ^ p;
	int u = A[R[v]] ^ B[R[v]] ^ v;
	if (M[u] != 2)
		DFS2(u, R[v]);
}
int main()
{
	scanf("%d%d", &n, &m);
	if (m > n) return !printf("0\n");
	for (int i = 1; i <= n; i++)
		scanf("%lld", &C[i]);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &A[i], &B[i]);
		Adj[A[i]].pb(i);
		Adj[B[i]].pb(i);
	}
	DFSC(1, 0);
	if (!cv)
		cv = cu = 1;
	vector < int > vec;
	vec.pb(cu);
	while (cv != cu)
		cu = P[cu], vec.pb(cu);
	if ((int)vec.size() % 2 == 0)
		return !printf("0\n");
	memset(M, 0, sizeof(M));
	for (int v : vec)
		M[v] = 1;
	for (int v : vec)
		for (int id : Adj[v])
		{
			int u = A[id] ^ B[id] ^ v;
			if (!M[u]) DFS(u, id);
		}

	for (int i = 1; i <= 5; i++)
		printf("%lld ", C[i]);
	printf("\n");

	if (vec.size() > 1)
	{
		for (int v : vec)
		{
			for (int i = 0; i < (int)Adj[v].size(); i++)
			{
				int id = Adj[v][i];
				if (!M[A[id] ^ B[id] ^ v])
					swap(Adj[v][i], Adj[v].back()), Adj[v].pop_back(), i --;
			}
			assert(Adj[v].size() == 2);
		}
		int idd = Adj[vec[0]][0];
		if ((A[idd] ^ B[idd] ^ vec[0]) != vec[1])
			DFS2(vec[0], Adj[vec[0]][0]);
		else
			DFS2(vec[0], Adj[vec[0]][1]);
		vector < ll > Df(vec.size(), 0);
		for (int i = 2; i != 0; i = (i + 2) % (int)vec.size())
		{
			int p1 = i - 1;
			int p2 = i - 2;
			if (p1 < 0)
				p1 += (int)vec.size();
			if (p2 < 0)
				p2 += (int)vec.size();
			Df[i] = Df[p2] - C[vec[p2]] + C[vec[p1]];
		}
		ll sum = 0;
		for (int i = 0; i < (int)vec.size(); i++)
			sum += C[vec[i]];
		sum /= 2;
		for (int i = 0; i < (int)vec.size(); i++)
			sum -= Df[i];
		sum /= (int)vec.size();
		for (int i = 0; i < (int)vec.size(); i++)
			D[P[vec[i]]] += (sum + Df[i]) * 2;
	}
	for (int i = 1; i <= m; i++)
		printf("%lld\n", D[i]);
	return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:43: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:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &C[i]);
   ~~~~~^~~~~~~~~~~~~~~
pipes.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 3072 KB Output isn't correct
2 Incorrect 7 ms 3072 KB Output isn't correct
3 Incorrect 6 ms 3200 KB Output isn't correct
4 Incorrect 102 ms 9468 KB Output isn't correct
5 Incorrect 5 ms 3072 KB Output isn't correct
6 Incorrect 5 ms 3072 KB Output isn't correct
7 Incorrect 5 ms 3072 KB Output isn't correct
8 Incorrect 4 ms 3072 KB Output isn't correct
9 Incorrect 5 ms 3200 KB Output isn't correct
10 Incorrect 6 ms 3200 KB Output isn't correct
11 Incorrect 5 ms 3168 KB Output isn't correct
12 Incorrect 6 ms 3200 KB Output isn't correct
13 Incorrect 98 ms 8196 KB Output isn't correct
14 Incorrect 109 ms 9080 KB Output isn't correct
15 Incorrect 120 ms 9460 KB Output isn't correct
16 Incorrect 143 ms 8524 KB Output isn't correct
17 Incorrect 124 ms 9436 KB Output isn't correct
18 Incorrect 180 ms 9508 KB Output isn't correct
19 Incorrect 182 ms 11740 KB Output isn't correct
20 Incorrect 9 ms 3072 KB Output isn't correct
21 Incorrect 5 ms 3200 KB Output isn't correct
22 Incorrect 126 ms 9528 KB Output isn't correct
23 Incorrect 99 ms 8144 KB Output isn't correct
24 Incorrect 129 ms 9564 KB Output isn't correct
25 Incorrect 122 ms 8384 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 3072 KB Output isn't correct
2 Incorrect 5 ms 3200 KB Output isn't correct
3 Correct 89 ms 10460 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Incorrect 4 ms 3072 KB Output isn't correct
8 Incorrect 5 ms 3072 KB Output isn't correct
9 Correct 5 ms 2688 KB Output is correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 4 ms 2688 KB Output is correct
12 Correct 5 ms 2660 KB Output is correct
13 Correct 5 ms 2688 KB Output is correct
14 Incorrect 5 ms 3072 KB Output isn't correct
15 Incorrect 6 ms 3200 KB Output isn't correct
16 Incorrect 7 ms 3200 KB Output isn't correct
17 Correct 6 ms 2816 KB Output is correct
18 Correct 4 ms 2688 KB Output is correct
19 Correct 5 ms 2688 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 4 ms 2688 KB Output is correct
22 Incorrect 5 ms 3200 KB Output isn't correct
23 Incorrect 130 ms 11352 KB Output isn't correct
24 Incorrect 129 ms 12640 KB Output isn't correct
25 Correct 89 ms 10480 KB Output is correct
26 Correct 4 ms 2688 KB Output is correct
27 Correct 5 ms 2688 KB Output is correct
28 Correct 4 ms 2688 KB Output is correct
29 Correct 2 ms 2688 KB Output is correct
30 Incorrect 137 ms 14156 KB Output isn't correct
31 Incorrect 131 ms 14708 KB Output isn't correct
32 Incorrect 96 ms 10868 KB Output isn't correct
33 Correct 83 ms 11228 KB Output is correct
34 Correct 4 ms 2688 KB Output is correct
35 Correct 4 ms 2688 KB Output is correct
36 Correct 4 ms 2688 KB Output is correct
37 Correct 3 ms 2688 KB Output is correct
38 Incorrect 142 ms 13580 KB Output isn't correct
39 Incorrect 123 ms 10528 KB Output isn't correct
40 Incorrect 170 ms 12428 KB Output isn't correct
41 Correct 144 ms 12920 KB Output is correct
42 Correct 4 ms 2688 KB Output is correct
43 Correct 4 ms 2688 KB Output is correct
44 Correct 4 ms 2688 KB Output is correct
45 Correct 5 ms 2688 KB Output is correct
46 Incorrect 171 ms 14520 KB Output isn't correct
47 Incorrect 143 ms 12448 KB Output isn't correct
48 Incorrect 171 ms 14504 KB Output isn't correct
49 Correct 86 ms 8696 KB Output is correct
50 Correct 4 ms 2688 KB Output is correct
51 Correct 4 ms 2688 KB Output is correct
52 Correct 4 ms 2688 KB Output is correct
53 Correct 4 ms 2688 KB Output is correct
54 Incorrect 176 ms 13148 KB Output isn't correct