답안 #120946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
120946 2019-06-25T19:41:49 Z thiago4532 Pipes (BOI13_pipes) C++17
65 / 100
370 ms 26848 KB
#include <bits/stdc++.h>
#define int int64_t

using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int maxm = 5e5 + 10;
vector<int> grafo[maxn];
int n;
int s[maxn];
map<pair<int, int>, int> mapa;
int val[maxn], ans[maxn];

namespace tree{

int nivel[maxn], pai[maxn], soma[maxn];
void dfs(int u, int p = 0) {
	pai[u] = p;

	for(auto v : grafo[u]) {
		if(v == p) continue;
		nivel[v] = nivel[u] + 1;
		dfs(v, u);
	}
}

};

int32_t main() {
	int m;

	cin >> n >> m;
	if(m > n) {
		cout << "0\n";
		return 0;
	}
	int total = 0;
	for(int i=1;i<=n;i++)
		cin >> s[i], s[i] *= 2, total += s[i];

	for(int i=1;i<=m;i++) {
		int a, b;
		cin >> a >> b;
		grafo[a].push_back(b);
		grafo[b].push_back(a);
		mapa[{a, b}] = i;
		mapa[{b, a}] = i;
	}
	if(n - 1 == m) {
		tree::dfs(1);
		vector<pii> arr;
		for(int i=1;i<=n;i++)
			arr.push_back({tree::nivel[i], i});
		sort(arr.begin(), arr.end(), greater<pii>());

		for(auto e : arr) {
			int v = e.second;
			int u = tree::pai[v];

			tree::soma[u] += (s[v] - tree::soma[v]);
			ans[mapa[{u, v}]] = (s[v] - tree::soma[v]);
		}

		if(tree::soma[1] != s[1]){
			cout << "0\n";
			return 0;
		}

		for(int i=1;i<=m;i++)
			cout << ans[i] << "\n";

	}
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 5 ms 2944 KB Output is correct
4 Correct 349 ms 24932 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 5 ms 2944 KB Output is correct
10 Correct 6 ms 2944 KB Output is correct
11 Correct 5 ms 2944 KB Output is correct
12 Correct 5 ms 2944 KB Output is correct
13 Correct 268 ms 20456 KB Output is correct
14 Correct 323 ms 23780 KB Output is correct
15 Correct 359 ms 25060 KB Output is correct
16 Correct 296 ms 21604 KB Output is correct
17 Correct 344 ms 24936 KB Output is correct
18 Correct 358 ms 25064 KB Output is correct
19 Correct 350 ms 26848 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 5 ms 2944 KB Output is correct
22 Correct 364 ms 25052 KB Output is correct
23 Correct 255 ms 20324 KB Output is correct
24 Correct 370 ms 25032 KB Output is correct
25 Correct 288 ms 21348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2688 KB Output isn't correct
2 Incorrect 5 ms 2816 KB Output isn't correct
3 Incorrect 238 ms 18592 KB Output isn't correct
4 Correct 4 ms 2816 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 2688 KB Output isn't correct
8 Incorrect 4 ms 2688 KB Output isn't correct
9 Incorrect 4 ms 2688 KB Output isn't correct
10 Correct 5 ms 2688 KB Output is correct
11 Correct 4 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 2688 KB Output isn't correct
15 Incorrect 5 ms 2816 KB Output isn't correct
16 Incorrect 5 ms 2816 KB Output isn't correct
17 Incorrect 5 ms 2816 KB Output isn't 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 4 ms 2688 KB Output is correct
22 Incorrect 5 ms 2816 KB Output isn't correct
23 Incorrect 197 ms 16308 KB Output isn't correct
24 Incorrect 254 ms 19320 KB Output isn't correct
25 Incorrect 243 ms 18484 KB Output isn't correct
26 Correct 3 ms 2688 KB Output is correct
27 Correct 4 ms 2688 KB Output is correct
28 Correct 4 ms 2688 KB Output is correct
29 Correct 4 ms 2816 KB Output is correct
30 Incorrect 260 ms 18808 KB Output isn't correct
31 Incorrect 256 ms 19320 KB Output isn't correct
32 Incorrect 247 ms 19684 KB Output isn't correct
33 Incorrect 245 ms 19320 KB Output isn't correct
34 Correct 3 ms 2688 KB Output is correct
35 Correct 3 ms 2816 KB Output is correct
36 Correct 4 ms 2688 KB Output is correct
37 Correct 4 ms 2688 KB Output is correct
38 Incorrect 237 ms 19164 KB Output isn't correct
39 Incorrect 248 ms 19536 KB Output isn't correct
40 Incorrect 249 ms 19400 KB Output isn't correct
41 Incorrect 241 ms 19192 KB Output isn't correct
42 Correct 4 ms 2688 KB Output is correct
43 Correct 4 ms 2688 KB Output is correct
44 Correct 3 ms 2688 KB Output is correct
45 Correct 3 ms 2688 KB Output is correct
46 Incorrect 240 ms 19036 KB Output isn't correct
47 Incorrect 241 ms 19448 KB Output isn't correct
48 Incorrect 292 ms 19192 KB Output isn't correct
49 Incorrect 233 ms 18744 KB Output isn't correct
50 Correct 3 ms 2688 KB Output is correct
51 Correct 3 ms 2688 KB Output is correct
52 Correct 3 ms 2688 KB Output is correct
53 Correct 3 ms 2688 KB Output is correct
54 Incorrect 247 ms 19064 KB Output isn't correct