oj.uz

Submission #443797

# Submission time Handle Problem Language Result Execution time Memory
443797 2021-07-12T06:25:29 Z wind_reaper Pipes (BOI13_pipes) C++17
74.0741 / 100
 554 ms 131076 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;

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;

		vector<int> a, b;

		while(u != x || a.empty()){
			auto [v, idx] = a.empty() || (*g[u].begin())[0] != a.back() ? *g[u].begin() : *g[u].rbegin();
			a.push_back(v);
			b.push_back(idx);
			u = v;
		}

		N = a.size();
		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:72:16: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |   while(u != x || a.empty()){
      |         ~~~~~~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 127 ms 16072 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 13888 KB Output is correct
14 Correct 115 ms 15544 KB Output is correct
15 Correct 125 ms 16208 KB Output is correct
16 Correct 107 ms 14420 KB Output is correct
17 Correct 115 ms 16060 KB Output is correct
18 Correct 113 ms 16196 KB Output is correct
19 Correct 94 ms 15688 KB Output is correct
20 Correct 3 ms 5004 KB Output is correct
21 Correct 4 ms 5068 KB Output is correct
22 Correct 122 ms 16108 KB Output is correct
23 Correct 89 ms 13848 KB Output is correct
24 Correct 121 ms 16176 KB Output is correct
25 Correct 101 ms 14276 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 261 ms 131076 KB Execution killed with signal 9
2 Runtime error 265 ms 131076 KB Execution killed with signal 9
3 Correct 86 ms 14932 KB Output is correct
4 Correct 75 ms 14660 KB Output is correct
5 Correct 69 ms 14512 KB Output is correct
6 Correct 497 ms 52264 KB Output is correct
7 Runtime error 265 ms 131076 KB Execution killed with signal 9
8 Runtime error 266 ms 131076 KB Execution killed with signal 9
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 4 ms 5008 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Runtime error 268 ms 131076 KB Execution killed with signal 9
15 Runtime error 261 ms 131076 KB Execution killed with signal 9
16 Runtime error 261 ms 131076 KB Execution killed with signal 9
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 258 ms 131076 KB Execution killed with signal 9
23 Runtime error 334 ms 131076 KB Execution killed with signal 9
24 Runtime error 345 ms 131076 KB Execution killed with signal 9
25 Correct 88 ms 14904 KB Output is correct
26 Correct 71 ms 14720 KB Output is correct
27 Correct 83 ms 14684 KB Output is correct
28 Correct 100 ms 15252 KB Output is correct
29 Correct 367 ms 43076 KB Output is correct
30 Runtime error 331 ms 131076 KB Execution killed with signal 9
31 Runtime error 329 ms 131076 KB Execution killed with signal 9
32 Runtime error 373 ms 131076 KB Execution killed with signal 9
33 Correct 93 ms 15408 KB Output is correct
34 Correct 81 ms 14764 KB Output is correct
35 Correct 75 ms 14700 KB Output is correct
36 Correct 92 ms 14848 KB Output is correct
37 Correct 554 ms 52312 KB Output is correct
38 Runtime error 341 ms 131076 KB Execution killed with signal 9
39 Runtime error 379 ms 131076 KB Execution killed with signal 9
40 Runtime error 381 ms 131076 KB Execution killed with signal 9
41 Correct 87 ms 15328 KB Output is correct
42 Correct 76 ms 14812 KB Output is correct
43 Correct 94 ms 14848 KB Output is correct
44 Correct 72 ms 14600 KB Output is correct
45 Correct 488 ms 46972 KB Output is correct
46 Runtime error 344 ms 131076 KB Execution killed with signal 9
47 Runtime error 344 ms 131076 KB Execution killed with signal 9
48 Runtime error 328 ms 131076 KB Execution killed with signal 9
49 Correct 108 ms 15176 KB Output is correct
50 Correct 74 ms 14876 KB Output is correct
51 Correct 75 ms 14836 KB Output is correct
52 Correct 92 ms 14624 KB Output is correct
53 Correct 471 ms 47948 KB Output is correct
54 Runtime error 349 ms 131076 KB Execution killed with signal 9