oj.uz

Submission #120977

# Submission time Handle Problem Language Result Execution time Memory
120977 2019-06-25T20:38:12 Z thiago4532 Pipes (BOI13_pipes) C++17
66.2963 / 100
 387 ms 30192 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], s2[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;
	}
}

};

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];

		ans[mapa[{u, v}]] = s[v];
	}
	for(auto v : grafo[u])
		if(ciclo[v]) s[v] -= s[u], ans[mapa[{u, 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, s2[i] = s[i], 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();
		for(int u=1;u<=n;u++){
			int sum = 0;
			for(auto v : grafo[u]){
				sum += ans[mapa[{u, v}]];
			}
			if(sum != s2[u]) {
				cout << "0\n";
				return 0;
			}
		}
		for(int i=1;i<=n;i++)
			cout << ans[i] << "\n";
	}
	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 2816 KB Output is correct
3 Correct 6 ms 2944 KB Output is correct
4 Correct 387 ms 26624 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 4 ms 2816 KB Output is correct
8 Correct 4 ms 2788 KB Output is correct
9 Correct 5 ms 2944 KB Output is correct
10 Correct 6 ms 2944 KB Output is correct
11 Correct 6 ms 2944 KB Output is correct
12 Correct 5 ms 2944 KB Output is correct
13 Correct 284 ms 21732 KB Output is correct
14 Correct 327 ms 25320 KB Output is correct
15 Correct 352 ms 26600 KB Output is correct
16 Correct 288 ms 23012 KB Output is correct
17 Correct 350 ms 26600 KB Output is correct
18 Correct 350 ms 26596 KB Output is correct
19 Correct 375 ms 28408 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 5 ms 2944 KB Output is correct
22 Correct 359 ms 26568 KB Output is correct
23 Correct 270 ms 21604 KB Output is correct
24 Correct 371 ms 26596 KB Output is correct
25 Correct 307 ms 22632 KB Output is correct

Subtask #2
36.2962962963 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2688 KB Output isn't correct
2 Incorrect 5 ms 2944 KB Output isn't correct
3 Incorrect 269 ms 24304 KB Output isn't correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 3 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Incorrect 3 ms 2688 KB Output isn't correct
8 Correct 4 ms 2816 KB Output is correct
9 Incorrect 3 ms 2688 KB Output isn't correct
10 Correct 4 ms 2688 KB Output is correct
11 Correct 3 ms 2688 KB Output is correct
12 Correct 4 ms 2688 KB Output is correct
13 Correct 4 ms 2688 KB Output is correct
14 Incorrect 5 ms 2816 KB Output isn't correct
15 Incorrect 6 ms 2944 KB Output isn't correct
16 Incorrect 5 ms 2944 KB Output isn't correct
17 Incorrect 5 ms 2944 KB Output isn't correct
18 Correct 4 ms 2688 KB Output is correct
19 Correct 4 ms 2688 KB Output is correct
20 Correct 3 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 265 ms 22004 KB Output isn't correct
24 Incorrect 354 ms 25972 KB Output isn't correct
25 Incorrect 301 ms 24304 KB Output isn't correct
26 Correct 6 ms 2688 KB Output is correct
27 Correct 4 ms 2688 KB Output is correct
28 Correct 4 ms 2688 KB Output is correct
29 Correct 4 ms 2688 KB Output is correct
30 Incorrect 366 ms 28016 KB Output isn't correct
31 Incorrect 346 ms 27632 KB Output isn't correct
32 Incorrect 337 ms 24156 KB Output isn't correct
33 Incorrect 307 ms 25972 KB Output isn't correct
34 Correct 4 ms 2816 KB Output is correct
35 Correct 4 ms 2688 KB Output is correct
36 Correct 3 ms 2688 KB Output is correct
37 Correct 4 ms 2688 KB Output is correct
38 Incorrect 320 ms 25452 KB Output isn't correct
39 Incorrect 333 ms 23684 KB Output isn't correct
40 Incorrect 337 ms 25716 KB Output isn't correct
41 Incorrect 286 ms 27500 KB Output isn't correct
42 Correct 4 ms 2688 KB Output is correct
43 Correct 3 ms 2688 KB Output is correct
44 Correct 3 ms 2688 KB Output is correct
45 Correct 4 ms 2680 KB Output is correct
46 Incorrect 363 ms 30192 KB Output isn't correct
47 Incorrect 320 ms 26020 KB Output isn't correct
48 Incorrect 325 ms 27372 KB Output isn't correct
49 Incorrect 306 ms 22904 KB Output isn't 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 3 ms 2688 KB Output is correct
54 Incorrect 356 ms 26736 KB Output isn't correct