oj.uz

Submission #120970

# Submission time Handle Problem Language Result Execution time Memory
120970 2019-06-25T20:26:49 Z thiago4532 Pipes (BOI13_pipes) C++17
74.0741 / 100
 394 ms 27624 KB 
#include <bits/stdc++.h>
#define int int64_t

using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
const int maxm = 5e5 + 10;
vector<int> grafo[maxn];
int n;
int s[maxn];
map<pair<int, int>, int> mapa;
int val[maxn], ans[maxn];
int grau[maxn];

namespace tree{

int nivel[maxn], pai[maxn], soma[maxn];
void dfs(int u, int p = 0) {
	pai[u] = p;

	for(auto v : grafo[u]) {
		if(v == p) continue;
		nivel[v] = nivel[u] + 1;
		dfs(v, u);
	}
}

};

vector<int> ordem;
namespace cycle {
int st;

void solve() {
	if(ordem.size() % 2 == 0){
		cout << "0\n";
		return;
	}

	int x = 0;
	int sig = 1;
	for(auto& u : ordem){
		x += s[u]*sig;
		sig *= -1;
	}
	x/=2;

	ans[mapa[{ordem[0], ordem.back()}]] = x;
	// cout << ordem[0] << " " << ordem.back() << ": " << ans[mapa[{ordem[0], ordem.back()}]] << "\n";
	for(int i = 0; i < (int)ordem.size() - 1; i++) {
		ans[mapa[{ordem[i], ordem[i+1]}]] = s[ordem[i]] - x;
		// cout << ordem[i] << " " << ordem[i+1] << ": " << s[ordem[i]] - x << "\n";
		x = s[ordem[i]] - x;
	}

	for(int i=1;i<=n;i++){
		cout << ans[i] << "\n";
	}
}

};

bool mark[maxn], mark2[maxn];

int dfs(int u, int l = 0) {
	mark[u] = true;
	mark2[u] = true;

	for(auto v : grafo[u]){
		if(mark2[v] && v != l) {
			mark2[u] = false;
			ordem.push_back(u);
			return v;
		}else if(mark[v]) continue;

		int x = dfs(v, u);
		if(x != 0){
			mark2[u] = false;
			ordem.push_back(u);
			return (u == x ? 0 : x);
		}
	}

	mark2[u] = false;
	return 0;
}

bool test[maxn];
int ciclo[maxn];

void dfs2(int u) {
	test[u] = true;
	for(auto v : grafo[u]) {
		if(test[v] || ciclo[v]) continue;
	
		dfs2(v);
		s[u] -= s[v];
	}
	for(auto v : grafo[u])
		if(ciclo[v]) s[v] -= s[u];
}

int32_t main() {
	int m;

	cin >> n >> m;
	if(m > n) {
		cout << "0\n";
		return 0;
	}
	int total = 0;
	for(int i=1;i<=n;i++)
		cin >> s[i], s[i] *= 2, total += s[i];

	for(int i=1;i<=m;i++) {
		int a, b;
		cin >> a >> b;
		grafo[a].push_back(b);
		grafo[b].push_back(a);
		mapa[{a, b}] = i;
		mapa[{b, a}] = i;

		grau[a]++;
		grau[b]++;
	}
	if(n - 1 == m) {
		tree::dfs(1);
		vector<pii> arr;
		for(int i=1;i<=n;i++)
			arr.push_back({tree::nivel[i], i});
		sort(arr.begin(), arr.end(), greater<pii>());

		for(auto e : arr) {
			int v = e.second;
			int u = tree::pai[v];

			tree::soma[u] += (s[v] - tree::soma[v]);
			ans[mapa[{u, v}]] = (s[v] - tree::soma[v]);
		}

		if(tree::soma[1] != s[1]){
			cout << "0\n";
			return 0;
		}

		for(int i=1;i<=m;i++)
			cout << ans[i] << "\n";

	}else { // n == m
		dfs(1);
		// for(auto& u : ordem){
		// 	cout << u << "\n";
		// }
		for(auto& o : ordem)
			ciclo[o] = true;

		for(int u=1;u<=n;u++) {
			if(ciclo[u] || test[u]) continue;
			dfs2(u);
		}
		cycle::st = ordem[0];

		cycle::solve();
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 5 ms 2944 KB Output is correct
4 Correct 341 ms 25848 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 5 ms 2944 KB Output is correct
10 Correct 5 ms 3072 KB Output is correct
11 Correct 5 ms 2944 KB Output is correct
12 Correct 6 ms 2960 KB Output is correct
13 Correct 261 ms 21096 KB Output is correct
14 Correct 334 ms 24552 KB Output is correct
15 Correct 352 ms 25820 KB Output is correct
16 Correct 301 ms 22244 KB Output is correct
17 Correct 352 ms 25700 KB Output is correct
18 Correct 365 ms 25828 KB Output is correct
19 Correct 394 ms 27624 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 5 ms 2944 KB Output is correct
22 Correct 354 ms 25776 KB Output is correct
23 Correct 295 ms 21092 KB Output is correct
24 Correct 352 ms 25828 KB Output is correct
25 Correct 285 ms 22028 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2688 KB Output isn't correct
2 Incorrect 5 ms 2916 KB Output isn't correct
3 Correct 275 ms 22868 KB Output is correct
4 Correct 3 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 3 ms 2688 KB Output is correct
7 Incorrect 3 ms 2688 KB Output isn't correct
8 Incorrect 4 ms 2688 KB Output isn't correct
9 Correct 4 ms 2688 KB Output is correct
10 Correct 3 ms 2688 KB Output is correct
11 Correct 4 ms 2688 KB Output is correct
12 Correct 3 ms 2688 KB Output is correct
13 Correct 4 ms 2688 KB Output is correct
14 Incorrect 4 ms 2816 KB Output isn't correct
15 Incorrect 5 ms 2944 KB Output isn't correct
16 Incorrect 5 ms 2944 KB Output isn't correct
17 Correct 5 ms 2944 KB Output is correct
18 Correct 3 ms 2688 KB Output is correct
19 Correct 4 ms 2688 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 3 ms 2688 KB Output is correct
22 Incorrect 5 ms 2944 KB Output isn't correct
23 Incorrect 243 ms 21644 KB Output isn't correct
24 Incorrect 343 ms 25580 KB Output isn't correct
25 Correct 242 ms 22896 KB Output is correct
26 Correct 3 ms 2688 KB Output is correct
27 Correct 4 ms 2688 KB Output is correct
28 Correct 3 ms 2688 KB Output is correct
29 Correct 4 ms 2688 KB Output is correct
30 Incorrect 312 ms 26356 KB Output isn't correct
31 Incorrect 356 ms 27248 KB Output isn't correct
32 Incorrect 297 ms 23540 KB Output isn't correct
33 Correct 265 ms 24412 KB Output is correct
34 Correct 3 ms 2688 KB Output is correct
35 Correct 4 ms 2688 KB Output is correct
36 Correct 4 ms 2688 KB Output is correct
37 Correct 4 ms 2688 KB Output is correct
38 Incorrect 318 ms 24912 KB Output isn't correct
39 Incorrect 298 ms 23032 KB Output isn't correct
40 Incorrect 308 ms 25208 KB Output isn't correct
41 Correct 281 ms 25908 KB Output is correct
42 Correct 4 ms 2688 KB Output is correct
43 Correct 4 ms 2688 KB Output is correct
44 Correct 4 ms 2688 KB Output is correct
45 Correct 4 ms 2688 KB Output is correct
46 Incorrect 311 ms 27120 KB Output isn't correct
47 Incorrect 319 ms 25348 KB Output isn't correct
48 Incorrect 328 ms 27044 KB Output isn't correct
49 Correct 267 ms 21284 KB Output is correct
50 Correct 4 ms 2688 KB Output is correct
51 Correct 4 ms 2688 KB Output is correct
52 Correct 4 ms 2688 KB Output is correct
53 Correct 4 ms 2688 KB Output is correct
54 Incorrect 308 ms 25556 KB Output isn't correct