oj.uz

Submission #443801

# Submission time Handle Problem Language Result Execution time Memory
443801 2021-07-12T06:31:48 Z wind_reaper Pipes (BOI13_pipes) C++17
74.0741 / 100
 504 ms 54300 KB 
#include <bits/stdc++.h>

using namespace std;

const int MXN = 100000;

set<array<int, 2>> g[MXN];
int change[MXN], suf[MXN];
bitset<MXN> vis;
int a[MXN], b[MXN];

void solve(){
	int N, M;
	cin >> N >> M;

	int ans[M];
	memset(ans, 0, sizeof ans);
	
	for(int i = 0; i < N; i++)
		cin >> change[i];

	for(int i = 0; i < M; i++){
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].insert({v, i});
		g[v].insert({u, i});
	}

	if(M > N){
		cout << 0 << '\n';
		return;
	}

	queue<array<int, 3>> q;
	for(int i = 0; i < N; i++)
		if(g[i].size() < 2){
			q.push({i, (*g[i].begin())[0], (*g[i].begin())[1]});
			vis[i] = 1;
		}

	int cnt = 0;

	while(!q.empty()){
		auto [u, par, idx] = q.front();
		q.pop();

		++cnt;

		int t = change[u];
		ans[idx] += 2*t;
		change[u] -= t;
		change[par] -= t;

		g[par].erase({u, idx});

		if(g[par].size() == 1 && !vis[par])
			q.push({par, (*g[par].begin())[0], (*g[par].begin())[1]});
	}

	if(cnt < N){
		if(!((N - cnt) & 1)){
			cout << 0 << '\n';
			return;
		}

		int x;
		for(int i = 0; i < N; i++) 
			if(!vis[i]) 
				x = i;

		int u = x;

		int cntr = 0;

		while(u != x || cntr == 0){
			auto [v, idx] = cntr == 0 || (*g[u].begin())[0] != a[cntr-1] ? *g[u].begin() : *g[u].rbegin();
			a[cntr] = v;
			b[cntr++] = idx;
			u = v;
		}

		N = cntr;
		suf[N-1] = change[a[N-1]];
		for(int i = N - 2; i >= 0; --i)
			suf[i] = change[a[i]] - suf[i+1];
		int pre = 0;

		for(int i = 0; i < N; i++){
			pre = change[a[i]] - pre;
			ans[b[i]] = (pre + (i + 1 < N ? suf[i+1] : 0));
		}
	}

	for(int i = 0; i < M; i++)
		cout << ans[i] << '\n';
}

int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 

	solve();

	return 0; 
}

Compilation message

pipes.cpp: In function 'void solve()':
pipes.cpp:76:16: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |   while(u != x || cntr == 0){
      |         ~~~~~~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 149 ms 16136 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 4 ms 4940 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 3 ms 5028 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 4 ms 5068 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 97 ms 13836 KB Output is correct
14 Correct 115 ms 15568 KB Output is correct
15 Correct 128 ms 16180 KB Output is correct
16 Correct 104 ms 14596 KB Output is correct
17 Correct 134 ms 16132 KB Output is correct
18 Correct 126 ms 16160 KB Output is correct
19 Correct 99 ms 15672 KB Output is correct
20 Correct 3 ms 4984 KB Output is correct
21 Correct 4 ms 5068 KB Output is correct
22 Correct 132 ms 16140 KB Output is correct
23 Correct 89 ms 13840 KB Output is correct
24 Correct 124 ms 16224 KB Output is correct
25 Correct 101 ms 14416 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 13132 KB Execution killed with signal 11
2 Runtime error 14 ms 13260 KB Execution killed with signal 11
3 Correct 102 ms 14960 KB Output is correct
4 Correct 70 ms 15104 KB Output is correct
5 Correct 71 ms 14916 KB Output is correct
6 Correct 503 ms 54208 KB Output is correct
7 Runtime error 14 ms 13132 KB Execution killed with signal 11
8 Runtime error 12 ms 13140 KB Execution killed with signal 11
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 3 ms 4940 KB Output is correct
14 Runtime error 12 ms 13168 KB Execution killed with signal 11
15 Runtime error 13 ms 13260 KB Execution killed with signal 11
16 Runtime error 13 ms 13264 KB Execution killed with signal 11
17 Correct 4 ms 5068 KB Output is correct
18 Correct 4 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 4 ms 5196 KB Output is correct
22 Runtime error 13 ms 13256 KB Execution killed with signal 11
23 Runtime error 80 ms 29620 KB Execution killed with signal 11
24 Runtime error 106 ms 33584 KB Execution killed with signal 11
25 Correct 92 ms 14916 KB Output is correct
26 Correct 75 ms 15112 KB Output is correct
27 Correct 86 ms 15012 KB Output is correct
28 Correct 87 ms 15576 KB Output is correct
29 Correct 392 ms 44664 KB Output is correct
30 Runtime error 93 ms 32708 KB Execution killed with signal 11
31 Runtime error 108 ms 33076 KB Execution killed with signal 11
32 Runtime error 115 ms 34072 KB Execution killed with signal 11
33 Correct 88 ms 15468 KB Output is correct
34 Correct 73 ms 15160 KB Output is correct
35 Correct 74 ms 15080 KB Output is correct
36 Correct 78 ms 15184 KB Output is correct
37 Correct 504 ms 54300 KB Output is correct
38 Runtime error 94 ms 33232 KB Execution killed with signal 11
39 Runtime error 127 ms 33888 KB Execution killed with signal 11
40 Runtime error 112 ms 33552 KB Execution killed with signal 11
41 Correct 91 ms 15148 KB Output is correct
42 Correct 72 ms 15168 KB Output is correct
43 Correct 72 ms 15136 KB Output is correct
44 Correct 73 ms 14872 KB Output is correct
45 Correct 473 ms 48596 KB Output is correct
46 Runtime error 94 ms 32964 KB Execution killed with signal 11
47 Runtime error 106 ms 33692 KB Execution killed with signal 11
48 Runtime error 86 ms 33092 KB Execution killed with signal 11
49 Correct 99 ms 15112 KB Output is correct
50 Correct 71 ms 15136 KB Output is correct
51 Correct 73 ms 15172 KB Output is correct
52 Correct 75 ms 15000 KB Output is correct
53 Correct 480 ms 49504 KB Output is correct
54 Runtime error 95 ms 33044 KB Execution killed with signal 11