oj.uz

Submission #285719

# Submission time Handle Problem Language Result Execution time Memory
285719 2020-08-29T13:52:16 Z kostia244 Pipes (BOI13_pipes) C++17
74.0741 / 100
 257 ms 39672 KB 
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
using ll = long long;
using namespace std;
const int maxn = 1<<19;
int n, m;
vector<array<ll, 2>> g[maxn];
ll val[maxn];
ll vis[maxn], C[maxn], h[maxn], back = -1, bb;
ll s = 0;
ll dfs(int v, int p) {
	ll cur = C[v];
	vis[v] = 1;
	if(h[v]&1) s -= C[v];
	else s += C[v];
	for(auto &[i, id] : g[v]) if(i != p) {
		if(!vis[i]) {
			h[i] = h[v]+1;
			ll t = dfs(i, v);
			cur += t;
			val[id] = t;
		} else if(h[i] < h[v]) {
			if(back != -1 || (h[i]&1) != (h[v]&1)) {cout << "0\n", exit(0);}
			back = id, bb = h[v]&1;
		}
	}
	return -cur;
}
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> C[i];
	for(int f, t, i = 0; i < m; i++) {
		cin >> f >> t;
		g[f].push_back({t, i});
		g[t].push_back({f, i});
	}
	dfs(1, 1);
	if(back != -1) val[back] = bb?-s:s;
	for(int i = 0; i < m; i++) cout << -2ll*val[i] << "\n"; cout << endl;
}
//?VK
//??V
//K?

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:41:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   41 |  for(int i = 0; i < m; i++) cout << -2ll*val[i] << "\n"; cout << endl;
      |  ^~~
pipes.cpp:41:58: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   41 |  for(int i = 0; i < m; i++) cout << -2ll*val[i] << "\n"; cout << endl;
      |                                                          ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12672 KB Output is correct
2 Correct 9 ms 12672 KB Output is correct
3 Correct 10 ms 12800 KB Output is correct
4 Correct 87 ms 21368 KB Output is correct
5 Correct 10 ms 12672 KB Output is correct
6 Correct 12 ms 12672 KB Output is correct
7 Correct 10 ms 12672 KB Output is correct
8 Correct 9 ms 12672 KB Output is correct
9 Correct 10 ms 12800 KB Output is correct
10 Correct 12 ms 12800 KB Output is correct
11 Correct 10 ms 12800 KB Output is correct
12 Correct 10 ms 12800 KB Output is correct
13 Correct 77 ms 19576 KB Output is correct
14 Correct 81 ms 20856 KB Output is correct
15 Correct 87 ms 21360 KB Output is correct
16 Correct 69 ms 20092 KB Output is correct
17 Correct 83 ms 21368 KB Output is correct
18 Correct 81 ms 21372 KB Output is correct
19 Correct 119 ms 24512 KB Output is correct
20 Correct 10 ms 12672 KB Output is correct
21 Correct 10 ms 12800 KB Output is correct
22 Correct 92 ms 21428 KB Output is correct
23 Correct 65 ms 19576 KB Output is correct
24 Correct 90 ms 21368 KB Output is correct
25 Correct 86 ms 19960 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 12672 KB Output isn't correct
2 Incorrect 10 ms 12800 KB Output isn't correct
3 Correct 74 ms 23220 KB Output is correct
4 Correct 83 ms 25720 KB Output is correct
5 Correct 57 ms 20728 KB Output is correct
6 Correct 254 ms 39664 KB Output is correct
7 Incorrect 9 ms 12672 KB Output isn't correct
8 Incorrect 9 ms 12672 KB Output isn't correct
9 Correct 9 ms 12672 KB Output is correct
10 Correct 9 ms 12672 KB Output is correct
11 Correct 9 ms 12672 KB Output is correct
12 Correct 10 ms 12672 KB Output is correct
13 Correct 9 ms 12672 KB Output is correct
14 Incorrect 9 ms 12672 KB Output isn't correct
15 Incorrect 9 ms 12800 KB Output isn't correct
16 Incorrect 10 ms 12800 KB Output isn't correct
17 Correct 10 ms 12800 KB Output is correct
18 Correct 10 ms 12800 KB Output is correct
19 Correct 10 ms 12928 KB Output is correct
20 Correct 9 ms 12800 KB Output is correct
21 Correct 10 ms 12800 KB Output is correct
22 Incorrect 10 ms 12800 KB Output isn't correct
23 Incorrect 73 ms 23032 KB Output isn't correct
24 Incorrect 90 ms 24824 KB Output isn't correct
25 Correct 72 ms 23288 KB Output is correct
26 Correct 82 ms 25208 KB Output is correct
27 Correct 80 ms 25464 KB Output is correct
28 Correct 63 ms 19708 KB Output is correct
29 Correct 210 ms 34232 KB Output is correct
30 Incorrect 98 ms 26616 KB Output isn't correct
31 Incorrect 101 ms 26872 KB Output isn't correct
32 Incorrect 89 ms 22392 KB Output isn't correct
33 Correct 74 ms 24440 KB Output is correct
34 Correct 84 ms 24568 KB Output is correct
35 Correct 86 ms 25720 KB Output is correct
36 Correct 69 ms 21112 KB Output is correct
37 Correct 257 ms 39672 KB Output is correct
38 Incorrect 95 ms 26104 KB Output isn't correct
39 Incorrect 87 ms 22008 KB Output isn't correct
40 Incorrect 89 ms 24568 KB Output isn't correct
41 Correct 78 ms 26476 KB Output is correct
42 Correct 83 ms 24952 KB Output is correct
43 Correct 94 ms 26064 KB Output is correct
44 Correct 67 ms 20792 KB Output is correct
45 Correct 219 ms 36600 KB Output is correct
46 Incorrect 103 ms 27376 KB Output isn't correct
47 Incorrect 95 ms 24568 KB Output isn't correct
48 Incorrect 103 ms 26748 KB Output isn't correct
49 Correct 69 ms 21368 KB Output is correct
50 Correct 88 ms 24568 KB Output is correct
51 Correct 85 ms 23032 KB Output is correct
52 Correct 74 ms 21752 KB Output is correct
53 Correct 237 ms 36088 KB Output is correct
54 Incorrect 102 ms 25592 KB Output isn't correct