oj.uz

Submission #443984

# Submission time Handle Problem Language Result Execution time Memory
443984 2021-07-12T19:07:15 Z aryan12 Pipes (BOI13_pipes) C++17
74.0741 / 100
 214 ms 29360 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 5;
int change[N], result[N];
vector<pair<int, int> > g[N];
int edgeChange[N], temp[N];
bool vis[N];
int n, m;

void dfs(int node, int par, int edgeNum) {
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i].first != par) {
			dfs(g[node][i].first, node, g[node][i].second);
		}
	}
	int netWithParent = change[node] - result[node];
	if(par != -1) {
		result[node] += netWithParent;
		edgeChange[edgeNum] = netWithParent;
		result[par] += netWithParent;
	}
}

void Tree() {
	dfs(1, -1, -1);
	if(result[1] != change[1]) {
		cout << "0\n";
		return;
	}
	for(int i = 1; i <= m; i++) {
		cout << edgeChange[i] * 2 << "\n";
	}
}

void Solve() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> change[i];
	}
	for(int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(make_pair(v, i));
		g[v].push_back(make_pair(u, i));
	}
	if(m == n - 1) {
		Tree();
		return;
	}
	if(m > n) {
		cout << "0\n";
		return;
	}
	int cnt = 0;
	queue<int> q;
	for(int i = 1; i <= n; i++) {
		vis[i] = false;
		temp[i] = g[i].size();
		if(temp[i] == 1) {
			q.push(i);
		}
	}
	while(!q.empty()) {
		int node = q.front();
		vis[node] = true;
		q.pop();
		cnt++;
		for(int i = 0; i < g[node].size(); i++) {
			if(!vis[g[node][i].first]) {
				temp[g[node][i].first]--;
				if(temp[g[node][i].first] == 1) {
					q.push(g[node][i].first);
				}
				int netChange = change[node] - result[node];
				edgeChange[g[node][i].second] = netChange;
				result[node] += netChange;
				result[g[node][i].first] += netChange;
			}
		}
	}
	if((n - cnt) % 2 == 0) {
		cout << "0\n";
		return;
	}
	
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message

pipes.cpp: In function 'void dfs(long long int, long long int, long long int)':
pipes.cpp:15:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
pipes.cpp: In function 'void Solve()':
pipes.cpp:72:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i = 0; i < g[node].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 67 ms 10440 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2636 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 2 ms 2764 KB Output is correct
13 Correct 52 ms 8928 KB Output is correct
14 Correct 70 ms 10124 KB Output is correct
15 Correct 69 ms 10476 KB Output is correct
16 Correct 55 ms 9340 KB Output is correct
17 Correct 68 ms 10500 KB Output is correct
18 Correct 72 ms 10504 KB Output is correct
19 Correct 79 ms 13600 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 2 ms 2764 KB Output is correct
22 Correct 66 ms 10564 KB Output is correct
23 Correct 56 ms 8896 KB Output is correct
24 Correct 70 ms 10576 KB Output is correct
25 Correct 54 ms 9156 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 2 ms 2764 KB Output isn't correct
3 Correct 55 ms 10836 KB Output is correct
4 Correct 48 ms 8580 KB Output is correct
5 Correct 48 ms 8388 KB Output is correct
6 Correct 206 ms 29360 KB Output is correct
7 Incorrect 2 ms 2636 KB Output isn't correct
8 Incorrect 2 ms 2636 KB Output isn't correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Incorrect 2 ms 2636 KB Output isn't correct
15 Incorrect 2 ms 2764 KB Output isn't correct
16 Incorrect 2 ms 2764 KB Output isn't correct
17 Correct 2 ms 2764 KB Output is correct
18 Correct 2 ms 2636 KB Output is correct
19 Correct 3 ms 2636 KB Output is correct
20 Correct 2 ms 2636 KB Output is correct
21 Correct 3 ms 2764 KB Output is correct
22 Incorrect 2 ms 2764 KB Output isn't correct
23 Incorrect 43 ms 9592 KB Output isn't correct
24 Incorrect 57 ms 11224 KB Output isn't correct
25 Correct 53 ms 10756 KB Output is correct
26 Correct 48 ms 8608 KB Output is correct
27 Correct 51 ms 8500 KB Output is correct
28 Correct 49 ms 8844 KB Output is correct
29 Correct 170 ms 23972 KB Output is correct
30 Incorrect 57 ms 10760 KB Output isn't correct
31 Incorrect 53 ms 11112 KB Output isn't correct
32 Incorrect 62 ms 11268 KB Output isn't correct
33 Correct 58 ms 11172 KB Output is correct
34 Correct 48 ms 8644 KB Output is correct
35 Correct 47 ms 8644 KB Output is correct
36 Correct 48 ms 8600 KB Output is correct
37 Correct 214 ms 29328 KB Output is correct
38 Incorrect 59 ms 11076 KB Output isn't correct
39 Incorrect 61 ms 11316 KB Output isn't correct
40 Incorrect 56 ms 11204 KB Output isn't correct
41 Correct 51 ms 10996 KB Output is correct
42 Correct 48 ms 8516 KB Output is correct
43 Correct 48 ms 8500 KB Output is correct
44 Correct 47 ms 8388 KB Output is correct
45 Correct 172 ms 26820 KB Output is correct
46 Incorrect 59 ms 10944 KB Output isn't correct
47 Incorrect 58 ms 11192 KB Output isn't correct
48 Incorrect 52 ms 11076 KB Output isn't correct
49 Correct 56 ms 10852 KB Output is correct
50 Correct 46 ms 8656 KB Output is correct
51 Correct 49 ms 8568 KB Output is correct
52 Correct 47 ms 8516 KB Output is correct
53 Correct 171 ms 26052 KB Output is correct
54 Incorrect 56 ms 11064 KB Output isn't correct