Submission #1234225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234225		franuch	Brought Down the Grading Server? (CEOI23_balance)	C++20	10 / 100	2094 ms	17040 KiB

balance

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vc vector
#define st first
#define nd second
#define pll pair<ll, ll>
#define sz(a) (ll)a.size()
#define all(a) a.begin(), a.end()
#define pub push_back
#define pob pop_back

ll E, n, V;
vc<vc<ll>> a;

void input() {
	cin >> E >> n >> V;
	a.assign(E, vc<ll>(n));
	for (ll i = 0; i < E; i++)
		for (ll j = 0; j < n; j++) {
			cin >> a[i][j];
			a[i][j]--;
		}
}

struct Edge {
	ll v, i;
};

void solve() {
	vc<vc<Edge>> g(V, vc<Edge>());
	for (ll i = 0; i < E; i++) {
		ll v = a[i][0];
		ll w = a[i][1];
		g[v].pub({w, i});
		g[w].pub({v, i});
	}

	vc<ll> exp(V, 0);
	for (ll i = 0; i < E; i++)
		exp[a[i][0]]++, exp[a[i][1]]++;
	
	vc<ll> cur(V, 0);
	for (ll i = 0; i < E; i++)
		cur[a[i][0]]++;

	vc<bool> vis1;
	function<bool(ll)> dfs1 = [&](ll v) {
		vis1[v] = true;
		if (cur[v] < exp[v] / 2) {
			cur[v]++;
			return true;
		}
		for (auto &e : g[v]) {
			if (vis1[e.v] or a[e.i][0] != v)
				continue;
			if (dfs1(e.v)) {
				swap(a[e.i][0], a[e.i][1]);
				return true;
			}
		}
		return false;
	};
	
	vc<bool> vis2;
	function<bool(ll)> dfs2 = [&](ll v) {
		vis2[v] = true;
		if (cur[v] < (exp[v] + 1) / 2) {
			cur[v]++;
			return true;
		}
		for (auto &e : g[v]) {
			if (vis2[e.v] or a[e.i][0] != v)
				continue;
			if (dfs2(e.v)) {
				swap(a[e.i][0], a[e.i][1]);
				return true;
			}
		}
		return false;
	};
	
	while (true) {
		vis1.assign(V, false);
		vis2.assign(V, false);
		bool git = false;
		for (ll v = 0; v < V; v++) {
			if (not vis1[v] and cur[v] > exp[v] / 2 and dfs1(v)) {
				git = true;
				cur[v]--;
			}
			if (not vis2[v] and cur[v] > (exp[v] + 1) / 2 and dfs2(v)) {
				git = true;
				cur[v]--;
			}
		}
		if (not git)
			break;
	}
	for (auto &ai : a)
		cout << ai[0] + 1 << " " << ai[1] + 1 << "\n";	
}

void program() {
	input();
	solve();
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	program();
	return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2-1: 0 / 15
• Subtask 2-2: 0 / 5
• Subtask 2-3: 0 / 5
• Subtask 3-1: 0 / 15
• Subtask 3-2: 0 / 5
• Subtask 3-3: 0 / 5
• Subtask 4-1: 0 / 20
• Subtask 4-2: 0 / 10
• Subtask 4-3: 0 / 10