oj.uz

Submission #443981

# Submission time Handle Problem Language Result Execution time Memory
443981 2021-07-12T18:45:49 Z aryan12 Pipes (BOI13_pipes) C++17
65 / 100
 231 ms 32472 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];
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;
	}
}

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:14: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]
   14 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2816 KB Output is correct
4 Correct 84 ms 12140 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 2764 KB Output is correct
10 Correct 2 ms 2692 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 2 ms 2764 KB Output is correct
13 Correct 63 ms 10128 KB Output is correct
14 Correct 71 ms 11508 KB Output is correct
15 Correct 72 ms 12100 KB Output is correct
16 Correct 61 ms 10600 KB Output is correct
17 Correct 69 ms 12032 KB Output is correct
18 Correct 70 ms 12144 KB Output is correct
19 Correct 82 ms 15248 KB Output is correct
20 Correct 2 ms 2676 KB Output is correct
21 Correct 2 ms 2764 KB Output is correct
22 Correct 73 ms 12068 KB Output is correct
23 Correct 53 ms 10196 KB Output is correct
24 Correct 78 ms 12088 KB Output is correct
25 Correct 56 ms 10476 KB Output is correct

Subtask #2
35.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 2 ms 2696 KB Output isn't correct
3 Incorrect 46 ms 9716 KB Output isn't correct
4 Correct 53 ms 10168 KB Output is correct
5 Correct 48 ms 9920 KB Output is correct
6 Correct 216 ms 32380 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 Incorrect 2 ms 2636 KB Output isn't correct
10 Correct 2 ms 2684 KB Output is correct
11 Correct 2 ms 2680 KB Output is correct
12 Correct 2 ms 2636 KB Output is correct
13 Correct 2 ms 2636 KB Output is correct
14 Incorrect 3 ms 2636 KB Output isn't correct
15 Incorrect 2 ms 2764 KB Output isn't correct
16 Incorrect 2 ms 2636 KB Output isn't correct
17 Incorrect 2 ms 2636 KB Output isn't correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 2 ms 2636 KB Output is correct
20 Correct 2 ms 2764 KB Output is correct
21 Correct 3 ms 2764 KB Output is correct
22 Incorrect 2 ms 2636 KB Output isn't correct
23 Incorrect 47 ms 8704 KB Output isn't correct
24 Incorrect 51 ms 10160 KB Output isn't correct
25 Incorrect 48 ms 9668 KB Output isn't correct
26 Correct 47 ms 10180 KB Output is correct
27 Correct 47 ms 10104 KB Output is correct
28 Correct 50 ms 10432 KB Output is correct
29 Correct 175 ms 27168 KB Output is correct
30 Incorrect 49 ms 9924 KB Output isn't correct
31 Incorrect 50 ms 10160 KB Output isn't correct
32 Incorrect 49 ms 10080 KB Output isn't correct
33 Incorrect 48 ms 10228 KB Output isn't correct
34 Correct 49 ms 10232 KB Output is correct
35 Correct 47 ms 10168 KB Output is correct
36 Correct 53 ms 10180 KB Output is correct
37 Correct 231 ms 32472 KB Output is correct
38 Incorrect 47 ms 10180 KB Output isn't correct
39 Incorrect 46 ms 9972 KB Output isn't correct
40 Incorrect 53 ms 10204 KB Output isn't correct
41 Incorrect 53 ms 10076 KB Output isn't correct
42 Correct 51 ms 10140 KB Output is correct
43 Correct 49 ms 10080 KB Output is correct
44 Correct 48 ms 9924 KB Output is correct
45 Correct 159 ms 29840 KB Output is correct
46 Incorrect 47 ms 10048 KB Output isn't correct
47 Incorrect 50 ms 10100 KB Output isn't correct
48 Incorrect 53 ms 10172 KB Output isn't correct
49 Incorrect 58 ms 9800 KB Output isn't correct
50 Correct 47 ms 10180 KB Output is correct
51 Correct 49 ms 10104 KB Output is correct
52 Correct 47 ms 10096 KB Output is correct
53 Correct 185 ms 29016 KB Output is correct
54 Incorrect 60 ms 10052 KB Output isn't correct