Submission #203215

#	Time	Username	Problem	Language	Result	Execution time	Memory
203215		maruii	Teoretičar (COCI18_teoreticar)	C++14	130 / 130	4854 ms	59880 KiB

teoreticar

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

int L, R, M, ans[500005], cnt, D[200005];
bool vis[500005];
pii in[500005];
vector<pii> edge[200005];
void dfs(int x, int c, vector<int> &a, vector<int> &b) {
	while (edge[x].size()) {
		auto i = edge[x].back(); edge[x].pop_back();
		if (vis[i.ss]) continue;
		vis[i.ss] = 1;
		if (c) a.push_back(i.ss);
		else b.push_back(i.ss);
		D[x]--;
		D[i.ff]--;
		dfs(i.ff, c ^ 1, a, b);
		break;
	}
}
void solve(vector<int> &v) {
	for (auto i : v) vis[i] = 0;
	vector<int> u;
	int flag = 1;
	for (auto i : v) {
		int x = in[i].ff, y = in[i].ss;
		if (!D[x]) u.push_back(x);
		if (!D[y]) u.push_back(y);
		if (D[x] || D[y]) flag = 0;
		edge[x].emplace_back(y, i);
		edge[y].emplace_back(x, i);
		D[x]++, D[y]++;
	}
	if (flag) {
		for (auto i : u) edge[i].clear(), D[i] = 0;
		++cnt;
		for (auto i : v) ans[i] = cnt;
		return;
	}
	vector<int> a, b;
	for (auto i : u) if (D[i] & 1) dfs(i, 0, a, b);
	for (auto i : u) while (D[i]) dfs(i, 0, a, b);
	for (auto i : u) edge[i].clear();
	solve(a);
	solve(b);
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> L >> R >> M;
	vector<int> v;
	for (int i = 0; i < M; ++i) {
		int x, y; cin >> x >> y;
		in[i] = pii(x, L + y);
		v.emplace_back(i);
	}
	solve(v);
	printf("%d\n", *max_element(ans, ans + M));
	for (int i = 0; i < M; ++i) printf("%d\n", ans[i]);
	return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13