Submission #434389

# Submission time Handle Problem Language Result Execution time Memory
434389 2021-06-21T07:53:44 Z dutch Pipes (BOI13_pipes) C++17
100 / 100
618 ms 74636 KB
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int MAXN = 1e5;

set<array<int, 2>> h[MAXN];
int c[MAXN], ans[MAXN+1], cnt = 0, suf[MAXN];
bitset<MAXN> vis;

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m, x, y; cin >> n >> m;
	for(int i=0; i<n; ++i) cin >> c[i];
	for(int i=0; i<m; ++i){
		cin >> x >> y; --x, --y;
		h[x].insert({y, i});
		h[y].insert({x, i});
	}

	if(m > n){
		cout << 0;
		return 0;
	}

	queue<int> q; set<int> s;
	for(int i=0; i<n; ++i) if(h[i].size() < 2) q.push(i), vis[i] = 1;

	while(!q.empty()){
		int u = q.front(); q.pop();
		++cnt;
		array<int, 2> e = *h[u].begin();
		ans[e[1]] += c[u];
		c[e[0]] -= c[u];
		h[e[0]].erase({u, e[1]});
		if(h[e[0]].size() < 2 && !vis[e[0]]) q.push(e[0]), vis[e[0]] = 1;
	}

	if(cnt < n){
		if(!((n-cnt) & 1)){
			cout << 0;
			return 0;
		}
		for(int i=0; i<n; ++i) if(!vis[i]) x = i;
		int u = x;
		vector<int> a, b;
		while(u != x || a.empty()){
			auto v = a.empty() || (*h[u].begin())[0] != a.back() ? *h[u].begin() : *h[u].rbegin();
			a.push_back(u);
			b.push_back(v[1]);
			u = v[0];
		}
		n = a.size();
		int pre = 0;
		suf[n-1] = c[a[n-1]];
		for(int i=n-2; i>=0; --i) suf[i] = c[a[i]] - suf[i+1];
		for(int i=0; i<n; ++i){
			pre = c[a[i]] - pre;
			ans[b[i]] = (pre + (i+1 < n ? suf[i+1] : 0LL))/2LL;
		}
	}

 	for(int i=0; i<m; ++i) cout << 2*ans[i] << '\n';
}
# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 5 ms 5068 KB Output is correct
4 Correct 144 ms 21416 KB Output is correct
5 Correct 4 ms 5016 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5152 KB Output is correct
11 Correct 4 ms 5164 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct
13 Correct 106 ms 18012 KB Output is correct
14 Correct 140 ms 20532 KB Output is correct
15 Correct 171 ms 21548 KB Output is correct
16 Correct 115 ms 18968 KB Output is correct
17 Correct 147 ms 21544 KB Output is correct
18 Correct 139 ms 21504 KB Output is correct
19 Correct 121 ms 21104 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 4 ms 5152 KB Output is correct
22 Correct 144 ms 21476 KB Output is correct
23 Correct 122 ms 18008 KB Output is correct
24 Correct 146 ms 21500 KB Output is correct
25 Correct 115 ms 18764 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 5164 KB Output is correct
3 Correct 108 ms 20016 KB Output is correct
4 Correct 91 ms 19928 KB Output is correct
5 Correct 82 ms 19460 KB Output is correct
6 Correct 568 ms 74564 KB Output is correct
7 Correct 3 ms 5012 KB Output is correct
8 Correct 3 ms 5012 KB Output is correct
9 Correct 3 ms 5036 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct
13 Correct 3 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 5196 KB Output is correct
16 Correct 4 ms 5196 KB Output is correct
17 Correct 4 ms 5068 KB Output is correct
18 Correct 5 ms 5068 KB Output is correct
19 Correct 4 ms 5068 KB Output is correct
20 Correct 4 ms 5068 KB Output is correct
21 Correct 5 ms 5324 KB Output is correct
22 Correct 4 ms 5196 KB Output is correct
23 Correct 101 ms 19152 KB Output is correct
24 Correct 138 ms 22200 KB Output is correct
25 Correct 100 ms 19892 KB Output is correct
26 Correct 82 ms 19928 KB Output is correct
27 Correct 78 ms 19752 KB Output is correct
28 Correct 95 ms 20556 KB Output is correct
29 Correct 470 ms 60984 KB Output is correct
30 Correct 131 ms 21744 KB Output is correct
31 Correct 118 ms 22904 KB Output is correct
32 Correct 138 ms 21496 KB Output is correct
33 Correct 101 ms 20764 KB Output is correct
34 Correct 80 ms 19916 KB Output is correct
35 Correct 82 ms 19840 KB Output is correct
36 Correct 84 ms 19972 KB Output is correct
37 Correct 618 ms 74636 KB Output is correct
38 Correct 122 ms 21944 KB Output is correct
39 Correct 144 ms 21456 KB Output is correct
40 Correct 131 ms 22096 KB Output is correct
41 Correct 89 ms 20620 KB Output is correct
42 Correct 80 ms 19820 KB Output is correct
43 Correct 85 ms 19908 KB Output is correct
44 Correct 77 ms 19396 KB Output is correct
45 Correct 598 ms 66208 KB Output is correct
46 Correct 120 ms 21796 KB Output is correct
47 Correct 131 ms 22140 KB Output is correct
48 Correct 119 ms 22800 KB Output is correct
49 Correct 116 ms 19996 KB Output is correct
50 Correct 81 ms 19780 KB Output is correct
51 Correct 82 ms 19872 KB Output is correct
52 Correct 83 ms 19524 KB Output is correct
53 Correct 518 ms 67524 KB Output is correct
54 Correct 121 ms 21492 KB Output is correct