oj.uz

Submission #230635

# Submission time Handle Problem Language Result Execution time Memory
230635 2020-05-10T16:49:56 Z ruler Pipes (BOI13_pipes) C++14
74.0741 / 100
 124 ms 21608 KB 
// IOI 2021
#include <bits/stdc++.h>
using namespace std;

#define int ll
#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 1e6 + 7;
 
////////////////////////////////////////////////////////////////////

const int N = 1e5 + 5;

int X[N], M[N], A[N], E[N], P[N], up = 1, dw = 1;
vector<int> G[N], C[N], Cyc;

void DFSCyc(int v, int p = 0) {
	M[v] = 1;
	for (int i : G[v]) {
		int u = v ^ E[i];
		if (u == p) continue;
		if (M[u]) dw = u, up = v;
		else P[u] = v, DFSCyc(u, v);
	}
}
void DFST(int v, int idx) {
	int p = v ^ E[idx];
	for (int i : G[v]) {
		int u = v ^ E[i];
		if (i != idx) DFST(u, i);
	}
	X[idx] = A[v], A[p] -= A[v], A[v] = 0;
}

int32_t main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));

	int n, m; cin >> n >> m;
	if (n < m) die(0);
	int s = 0;
	for (int i = 0; i < n; i++) cin >> A[i + 1], s += A[i + 1];
	if (s % 2 == 1) die(0);
	for (int i = 0; i < m; i++) {
		int v, u; cin >> v >> u;
		G[v].push_back(i), G[u].push_back(i);
		E[i] = v ^ u;
	}
	DFSCyc(1);
	Cyc.push_back(dw);
	while (up != dw) dw = P[dw], Cyc.push_back(dw);
	if ((sz(Cyc) & 1) == 0) die(0);
	for (int v : Cyc) M[v] = 2;
	for (int v : Cyc) {
		for (int i : G[v]) {
			int u = v ^ E[i];
			if (M[u] != 2) DFST(u, i);
			else C[v].push_back(i);
		}
	}
	if (m == n - 1) {
		for (int i = 0; i < m; i++) cout << 2 * X[i] << endl;
		return 0;
	}
	int sum = 0;
	for (int i = 0; i < sz(Cyc); i++) {
		int v = Cyc[i], u = Cyc[(i + 1) % sz(Cyc)];
		if ((v ^ C[v][1]) != u) swap(C[v][0], C[v][1]);
		if ((i & 1) == 0) sum += A[v];
		else sum -= A[v];
	}
	X[C[Cyc[0]][0]] = sum / 2;
	for (int v : Cyc) X[C[v][1]] = A[v] - X[C[v][0]];
	for (int i = 0; i < m; i++) cout << 2 * X[i] << endl;


	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 87 ms 14712 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 7 ms 5120 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 7 ms 5248 KB Output is correct
11 Correct 8 ms 5120 KB Output is correct
12 Correct 7 ms 5120 KB Output is correct
13 Correct 64 ms 12792 KB Output is correct
14 Correct 79 ms 14200 KB Output is correct
15 Correct 86 ms 14840 KB Output is correct
16 Correct 69 ms 13304 KB Output is correct
17 Correct 87 ms 14712 KB Output is correct
18 Correct 83 ms 14688 KB Output is correct
19 Correct 97 ms 16504 KB Output is correct
20 Correct 7 ms 5120 KB Output is correct
21 Correct 7 ms 5120 KB Output is correct
22 Correct 99 ms 14708 KB Output is correct
23 Correct 64 ms 12664 KB Output is correct
24 Correct 82 ms 14712 KB Output is correct
25 Correct 68 ms 13048 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5120 KB Output isn't correct
2 Incorrect 8 ms 5248 KB Output isn't correct
3 Correct 66 ms 15480 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 4992 KB Output is correct
6 Correct 7 ms 4992 KB Output is correct
7 Incorrect 7 ms 5120 KB Output isn't correct
8 Incorrect 7 ms 5120 KB Output isn't correct
9 Correct 7 ms 4992 KB Output is correct
10 Correct 8 ms 4992 KB Output is correct
11 Correct 7 ms 4992 KB Output is correct
12 Correct 7 ms 4992 KB Output is correct
13 Correct 7 ms 4992 KB Output is correct
14 Incorrect 7 ms 4992 KB Output isn't correct
15 Incorrect 8 ms 5248 KB Output isn't correct
16 Incorrect 7 ms 5120 KB Output isn't correct
17 Correct 7 ms 5120 KB Output is correct
18 Correct 7 ms 4992 KB Output is correct
19 Correct 7 ms 4992 KB Output is correct
20 Correct 7 ms 4992 KB Output is correct
21 Correct 8 ms 5120 KB Output is correct
22 Incorrect 8 ms 5248 KB Output isn't correct
23 Incorrect 87 ms 17008 KB Output isn't correct
24 Incorrect 106 ms 18928 KB Output isn't correct
25 Correct 76 ms 15456 KB Output is correct
26 Correct 7 ms 4992 KB Output is correct
27 Correct 7 ms 4992 KB Output is correct
28 Correct 8 ms 4992 KB Output is correct
29 Correct 7 ms 4992 KB Output is correct
30 Incorrect 110 ms 19824 KB Output isn't correct
31 Incorrect 124 ms 21608 KB Output isn't correct
32 Incorrect 92 ms 15984 KB Output isn't correct
33 Correct 82 ms 16380 KB Output is correct
34 Correct 7 ms 4992 KB Output is correct
35 Correct 7 ms 4992 KB Output is correct
36 Correct 7 ms 4992 KB Output is correct
37 Correct 7 ms 5120 KB Output is correct
38 Incorrect 109 ms 19440 KB Output isn't correct
39 Incorrect 89 ms 15480 KB Output isn't correct
40 Incorrect 110 ms 18544 KB Output isn't correct
41 Correct 88 ms 18292 KB Output is correct
42 Correct 7 ms 4992 KB Output is correct
43 Correct 7 ms 4992 KB Output is correct
44 Correct 7 ms 5120 KB Output is correct
45 Correct 7 ms 4992 KB Output is correct
46 Incorrect 116 ms 20208 KB Output isn't correct
47 Incorrect 110 ms 18672 KB Output isn't correct
48 Incorrect 123 ms 21380 KB Output isn't correct
49 Correct 69 ms 13816 KB Output is correct
50 Correct 7 ms 4992 KB Output is correct
51 Correct 7 ms 4992 KB Output is correct
52 Correct 7 ms 5248 KB Output is correct
53 Correct 7 ms 4992 KB Output is correct
54 Incorrect 108 ms 18792 KB Output isn't correct