oj.uz

Submission #853287

# Submission time Handle Problem Language Result Execution time Memory
853287 2023-09-23T23:14:03 Z NK_ Pipes (BOI13_pipes) C++17
75.3704 / 100
 71 ms 18384 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 18;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, M; cin >> N >> M;

	if (M > N) {
		cout << 0 << nl;
		exit(0-0);
	}

	// TREE OR 1 CYCLE

	vl A(N); for(auto& x : A) cin >> x;

	V<vpi> adj(N); for(int i = 0; i < M; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(mp(v, i));
		adj[v].pb(mp(u, i));
	}

	vl ans(M); vi vis(N);
	function<int(int)> fix = [&](int u) { // remove odd
		vis[u] = 1;
		for(auto v : adj[u]) if (!vis[v.f]) {
			ans[v.s] = fix(v.f);
			A[u] -= ans[v.s];
		}

		int need = (A[u] % 2 == 0 ? 0 : 1); A[u] -= need;
		return need;
	};

	if (fix(0)) {
		cout << 0 << nl;
		exit(0-0);
	}	



	vi deg(N); vi seen(N);
	for(int u = 0; u < N; u++) for(auto v : adj[u]) {
		if (u > v.f) deg[u]++, deg[v.f]++;
	}

	queue<int> q; 
	for(int u = 0; u < N; u++) if (deg[u] == 1) q.push(u);

	while(sz(q)) {
		int u = q.front(); q.pop();

		seen[u] = 1;
		for(auto& v : adj[u]) {
			if (!seen[v.f]) {
				deg[v.f]--; 
				ans[v.s] += A[u]; A[v.f] -= A[u]; A[u] = 0;
				if (deg[v.f] == 1) q.push(v.f);
			}
		}
	}

	// for(int i = 0; i < M; i++) cout << ans[i] << nl;
	// cout << nl;
	// for(int i = 0; i < N; i++) cout << A[i] << nl;
	// cout << nl;


	int len = N - accumulate(begin(seen), end(seen), 0);

	if (len == 0) {
		for(int i = 0; i < M; i++) cout << ans[i] * 2LL << nl;
		exit(0-0);
	}

	if (len % 2 == 0) {
		cout << 0 << nl;
		exit(0-0);
	}	

	
	vi P;
	function<void(int)> dfs = [&](int u) {
		if (sz(P) == 2*len) return;
		P.pb(u);
		for(auto& v : adj[u]) {
			if (sz(P) > 1 && v.s == P[sz(P)-2]) continue;
			P.pb(v.s); 
			dfs(v.f);
			if (sz(P) == 2*len) return;
		}
	};

	int r = find(begin(seen), end(seen), 0) - begin(seen);
	dfs(r);

	int amt = 0, coef = 1;
	for(int i = 0; i < 2 * len; i += 2) {
		amt += coef * A[P[i]]; coef = -coef;
	}

	amt /= 2;

	for(int i = 0; i < 2 * len; i += 2) {
		ans[P[i+1]] += A[P[i]] - amt;
		amt = A[P[i]] - amt ;
	}

	for(int i = 0; i < M; i++) cout << ans[i] * 2LL << nl;
	exit(0-0);
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 48 ms 11340 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 456 KB Output is correct
8 Correct 0 ms 456 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 556 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 38 ms 9008 KB Output is correct
14 Correct 46 ms 10832 KB Output is correct
15 Correct 60 ms 11368 KB Output is correct
16 Correct 40 ms 9724 KB Output is correct
17 Correct 47 ms 11308 KB Output is correct
18 Correct 54 ms 11344 KB Output is correct
19 Correct 46 ms 14412 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 48 ms 11400 KB Output is correct
23 Correct 34 ms 9040 KB Output is correct
24 Correct 48 ms 11348 KB Output is correct
25 Correct 36 ms 9560 KB Output is correct

Subtask #2
45.3703703704 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 504 KB Output isn't correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Correct 40 ms 13652 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 1 ms 344 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 456 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Incorrect 0 ms 456 KB Output isn't correct
15 Incorrect 1 ms 604 KB Output isn't correct
16 Incorrect 1 ms 344 KB Output isn't correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Incorrect 1 ms 588 KB Output isn't correct
23 Incorrect 38 ms 13560 KB Output isn't correct
24 Incorrect 65 ms 15616 KB Output isn't correct
25 Correct 41 ms 13536 KB Output is correct
26 Correct 1 ms 472 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 472 KB Output is correct
30 Incorrect 49 ms 17544 KB Output isn't correct
31 Incorrect 48 ms 18188 KB Output isn't correct
32 Incorrect 49 ms 12640 KB Output isn't correct
33 Correct 40 ms 14776 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Incorrect 52 ms 17008 KB Output isn't correct
39 Incorrect 46 ms 12112 KB Output isn't correct
40 Incorrect 51 ms 15052 KB Output isn't correct
41 Correct 43 ms 17028 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Incorrect 49 ms 18384 KB Output isn't correct
47 Correct 48 ms 15308 KB Output is correct
48 Incorrect 47 ms 17868 KB Output isn't correct
49 Correct 50 ms 11360 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Incorrect 71 ms 16384 KB Output isn't correct