oj.uz

Submission #443800

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

using namespace std;

const int MXN = 100000;

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

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

	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:73:16: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |   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 119 ms 16076 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 4996 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 4 ms 5024 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 91 ms 14040 KB Output is correct
14 Correct 112 ms 15488 KB Output is correct
15 Correct 127 ms 16192 KB Output is correct
16 Correct 109 ms 14548 KB Output is correct
17 Correct 124 ms 16272 KB Output is correct
18 Correct 129 ms 16332 KB Output is correct
19 Correct 103 ms 15772 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 5 ms 5068 KB Output is correct
22 Correct 120 ms 16324 KB Output is correct
23 Correct 89 ms 13824 KB Output is correct
24 Correct 125 ms 16232 KB Output is correct
25 Correct 97 ms 14284 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 13976 KB Execution killed with signal 11
2 Runtime error 14 ms 14156 KB Execution killed with signal 11
3 Correct 88 ms 15016 KB Output is correct
4 Correct 76 ms 14692 KB Output is correct
5 Correct 72 ms 14508 KB Output is correct
6 Correct 487 ms 52424 KB Output is correct
7 Runtime error 16 ms 13928 KB Execution killed with signal 11
8 Runtime error 14 ms 13960 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 13 ms 13940 KB Execution killed with signal 11
15 Runtime error 14 ms 14112 KB Execution killed with signal 11
16 Runtime error 14 ms 14056 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 5252 KB Output is correct
22 Runtime error 14 ms 14148 KB Execution killed with signal 11
23 Runtime error 80 ms 29776 KB Execution killed with signal 11
24 Runtime error 109 ms 35140 KB Execution killed with signal 11
25 Correct 89 ms 15004 KB Output is correct
26 Correct 73 ms 14716 KB Output is correct
27 Correct 69 ms 14660 KB Output is correct
28 Correct 77 ms 15168 KB Output is correct
29 Correct 385 ms 42976 KB Output is correct
30 Runtime error 100 ms 34244 KB Execution killed with signal 11
31 Runtime error 83 ms 33120 KB Execution killed with signal 11
32 Runtime error 125 ms 35468 KB Execution killed with signal 11
33 Correct 87 ms 15428 KB Output is correct
34 Correct 81 ms 14728 KB Output is correct
35 Correct 75 ms 14704 KB Output is correct
36 Correct 70 ms 14788 KB Output is correct
37 Correct 486 ms 52412 KB Output is correct
38 Runtime error 96 ms 34764 KB Execution killed with signal 11
39 Runtime error 127 ms 33920 KB Execution killed with signal 11
40 Runtime error 106 ms 33640 KB Execution killed with signal 11
41 Correct 72 ms 15172 KB Output is correct
42 Correct 70 ms 14780 KB Output is correct
43 Correct 76 ms 14788 KB Output is correct
44 Correct 75 ms 14528 KB Output is correct
45 Correct 467 ms 46928 KB Output is correct
46 Runtime error 95 ms 32964 KB Execution killed with signal 11
47 Runtime error 104 ms 33620 KB Execution killed with signal 11
48 Runtime error 83 ms 33144 KB Execution killed with signal 11
49 Correct 108 ms 15044 KB Output is correct
50 Correct 77 ms 14656 KB Output is correct
51 Correct 72 ms 14756 KB Output is correct
52 Correct 72 ms 14608 KB Output is correct
53 Correct 488 ms 47844 KB Output is correct
54 Runtime error 96 ms 33092 KB Execution killed with signal 11