oj.uz

Submission #443803

# Submission time Handle Problem Language Result Execution time Memory
443803 2021-07-12T06:35:27 Z wind_reaper Pipes (BOI13_pipes) C++17
74.0741 / 100
 529 ms 54360 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]});
			vis[par] = 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:77:16: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |   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 4 ms 4940 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 114 ms 16100 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 4 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 90 ms 13856 KB Output is correct
14 Correct 108 ms 15496 KB Output is correct
15 Correct 117 ms 16180 KB Output is correct
16 Correct 106 ms 14516 KB Output is correct
17 Correct 124 ms 16132 KB Output is correct
18 Correct 116 ms 16196 KB Output is correct
19 Correct 107 ms 15580 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 4 ms 5068 KB Output is correct
22 Correct 126 ms 16340 KB Output is correct
23 Correct 88 ms 13892 KB Output is correct
24 Correct 123 ms 16148 KB Output is correct
25 Correct 114 ms 14296 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 13096 KB Execution killed with signal 11
2 Runtime error 13 ms 13308 KB Execution killed with signal 11
3 Correct 88 ms 14944 KB Output is correct
4 Correct 76 ms 15080 KB Output is correct
5 Correct 77 ms 14888 KB Output is correct
6 Correct 508 ms 54360 KB Output is correct
7 Runtime error 12 ms 13092 KB Execution killed with signal 11
8 Runtime error 13 ms 13088 KB Execution killed with signal 11
9 Correct 3 ms 4940 KB Output is correct
10 Correct 4 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 13176 KB Execution killed with signal 11
15 Runtime error 12 ms 13356 KB Execution killed with signal 11
16 Runtime error 12 ms 13272 KB Execution killed with signal 11
17 Correct 3 ms 5068 KB Output is correct
18 Correct 3 ms 5068 KB Output is correct
19 Correct 3 ms 5068 KB Output is correct
20 Correct 3 ms 5132 KB Output is correct
21 Correct 4 ms 5196 KB Output is correct
22 Runtime error 15 ms 13280 KB Execution killed with signal 11
23 Runtime error 91 ms 29640 KB Execution killed with signal 11
24 Runtime error 119 ms 33476 KB Execution killed with signal 11
25 Correct 81 ms 14920 KB Output is correct
26 Correct 67 ms 15164 KB Output is correct
27 Correct 73 ms 15044 KB Output is correct
28 Correct 74 ms 15656 KB Output is correct
29 Correct 374 ms 44512 KB Output is correct
30 Runtime error 93 ms 32704 KB Execution killed with signal 11
31 Runtime error 82 ms 33016 KB Execution killed with signal 11
32 Runtime error 122 ms 33892 KB Execution killed with signal 11
33 Correct 95 ms 15460 KB Output is correct
34 Correct 71 ms 15120 KB Output is correct
35 Correct 77 ms 15212 KB Output is correct
36 Correct 78 ms 15148 KB Output is correct
37 Correct 529 ms 54304 KB Output is correct
38 Runtime error 106 ms 33296 KB Execution killed with signal 11
39 Runtime error 125 ms 33860 KB Execution killed with signal 11
40 Runtime error 109 ms 33572 KB Execution killed with signal 11
41 Correct 80 ms 15172 KB Output is correct
42 Correct 76 ms 15108 KB Output is correct
43 Correct 68 ms 15172 KB Output is correct
44 Correct 86 ms 14820 KB Output is correct
45 Correct 477 ms 48680 KB Output is correct
46 Runtime error 98 ms 32980 KB Execution killed with signal 11
47 Runtime error 111 ms 33528 KB Execution killed with signal 11
48 Runtime error 97 ms 33092 KB Execution killed with signal 11
49 Correct 100 ms 15020 KB Output is correct
50 Correct 74 ms 15152 KB Output is correct
51 Correct 76 ms 15172 KB Output is correct
52 Correct 91 ms 15044 KB Output is correct
53 Correct 468 ms 49484 KB Output is correct
54 Runtime error 113 ms 33092 KB Execution killed with signal 11