Submission #1245045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245045		kaiboy	Pipes (BOI13_pipes)	C++20	98.70 / 100	139 ms	24816 KiB

pipes

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 200000;
const int M = 1000000;

int aa[N], cc[N], ii[M], jj[M], ww[M], hh[M], n_, m_, *eh[N], eo[N];

void append(int i, int h) {
	int o = eo[i]++;
	if (!o)
		eh[i] = (int *) malloc(sizeof *eh[i]);
	else if (!(o & o - 1))
		eh[i] = (int *) realloc(eh[i], (o << 1) * sizeof *eh[i]);
	eh[i][o] = h;
}

void dfs0(int i, int c) {
	if (cc[i] != -1)
		return;
	n_++, cc[i] = c, c ^= 1;
	for (int o = 0; o < eo[i]; o++) {
		int h = eh[i][o];
		if (ww[h] == -1)
			ww[hh[m_++] = h] = 0;
		dfs0(i ^ ii[h] ^ jj[h], c);
	}
}

void dfs1(int h_, int i) {
	for (int o = 0; o < eo[i]; o++) {
		int h = eh[i][o];
		if (h != h_ && ii[h] != -1) {
			int j = i ^ ii[h] ^ jj[h];
			dfs1(h, j);
			ww[h] = aa[j];
			aa[i] -= ww[h];
			aa[j] -= ww[h];
		}
	}
}

bool dfs2(int i, int t, int w) {
	if (cc[i] == 2)
		return false;
	cc[i] = 2;
	if (i == t)
		return true;
	for (int o = 0; o < eo[i]; o++) {
		int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
		if (dfs2(j, t, -w)) {
			ww[h] += w;
			return true;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> aa[i], cc[i] = -1;
	for (int h = 0; h < m; h++) {
		int i, j; cin >> i >> j, i--, j--;
		append(ii[h] = i, h);
		append(jj[h] = j, h);
		ww[h] = -1;
	}
	for (int i = 0; i < n; i++)
		if (cc[i] == -1) {
			n_ = m_ = 0, dfs0(i, 0);
			if (m_ > n_) {
				cout << "0\n";
				return 0;
			}
			if (m_ == n_ - 1) {
				dfs1(-1, i);
				if (aa[i]) {
					cout << "0\n";
					return 0;
				}
				continue;
			}
			int h_ = -1;
			for (int z = 0; z < m_; z++) {
				int h = hh[z];
				if (cc[ii[h]] == cc[jj[h]]) {
					h_ = h;
					break;
				}
			}
			if (h_ == -1) {
				cout << "0\n";
				return 0;
			}
			int s = ii[h_], t = jj[h_]; ii[h_] = -1;
			dfs1(-1, s);
			int a = aa[s];
			if (a % 2) {
				cout << "0\n";
				return 0;
			}
			a /= 2;
			dfs2(s, t, a);
			ww[h_] += a;
		}
	for (int h = 0; h < m; h++)
		cout << ww[h] * 2 << '\n';
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 68.7037 / 70