oj.uz

Submission #443802

# Submission time Handle Problem Language Result Execution time Memory
443802 2021-07-12T06:34:27 Z wind_reaper Pipes (BOI13_pipes) C++17
74.0741 / 100
 499 ms 54340 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;
		N = 0;

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

		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:75:16: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |   while(u != x || N == 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 118 ms 16140 KB Output is correct
5 Correct 3 ms 4940 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 5068 KB Output is correct
11 Correct 4 ms 5068 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct
13 Correct 87 ms 13892 KB Output is correct
14 Correct 106 ms 15476 KB Output is correct
15 Correct 120 ms 16236 KB Output is correct
16 Correct 96 ms 14464 KB Output is correct
17 Correct 113 ms 16088 KB Output is correct
18 Correct 115 ms 16164 KB Output is correct
19 Correct 97 ms 15604 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 4 ms 5068 KB Output is correct
22 Correct 117 ms 16196 KB Output is correct
23 Correct 86 ms 13812 KB Output is correct
24 Correct 114 ms 16216 KB Output is correct
25 Correct 110 ms 14344 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 13 ms 13256 KB Execution killed with signal 11
3 Correct 84 ms 14896 KB Output is correct
4 Correct 70 ms 15172 KB Output is correct
5 Correct 75 ms 14856 KB Output is correct
6 Correct 499 ms 54340 KB Output is correct
7 Runtime error 12 ms 13132 KB Execution killed with signal 11
8 Runtime error 12 ms 13132 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 4 ms 4940 KB Output is correct
13 Correct 3 ms 4940 KB Output is correct
14 Runtime error 12 ms 13132 KB Execution killed with signal 11
15 Runtime error 13 ms 13360 KB Execution killed with signal 11
16 Runtime error 13 ms 13260 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 3 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 13364 KB Execution killed with signal 11
23 Runtime error 79 ms 29508 KB Execution killed with signal 11
24 Runtime error 98 ms 33540 KB Execution killed with signal 11
25 Correct 87 ms 14916 KB Output is correct
26 Correct 80 ms 15148 KB Output is correct
27 Correct 70 ms 15048 KB Output is correct
28 Correct 81 ms 15764 KB Output is correct
29 Correct 390 ms 44540 KB Output is correct
30 Runtime error 94 ms 32676 KB Execution killed with signal 11
31 Runtime error 85 ms 33064 KB Execution killed with signal 11
32 Runtime error 119 ms 33956 KB Execution killed with signal 11
33 Correct 88 ms 15440 KB Output is correct
34 Correct 69 ms 15140 KB Output is correct
35 Correct 70 ms 15072 KB Output is correct
36 Correct 72 ms 15236 KB Output is correct
37 Correct 492 ms 54232 KB Output is correct
38 Runtime error 100 ms 33244 KB Execution killed with signal 11
39 Runtime error 128 ms 33988 KB Execution killed with signal 11
40 Runtime error 105 ms 33628 KB Execution killed with signal 11
41 Correct 73 ms 15248 KB Output is correct
42 Correct 68 ms 15176 KB Output is correct
43 Correct 68 ms 15044 KB Output is correct
44 Correct 70 ms 14908 KB Output is correct
45 Correct 464 ms 48708 KB Output is correct
46 Runtime error 92 ms 33092 KB Execution killed with signal 11
47 Runtime error 99 ms 33636 KB Execution killed with signal 11
48 Runtime error 87 ms 33072 KB Execution killed with signal 11
49 Correct 95 ms 15120 KB Output is correct
50 Correct 71 ms 15044 KB Output is correct
51 Correct 70 ms 15052 KB Output is correct
52 Correct 68 ms 14964 KB Output is correct
53 Correct 449 ms 49476 KB Output is correct
54 Runtime error 98 ms 33200 KB Execution killed with signal 11