oj.uz

Submission #203206

# Submission time Handle Problem Language Result Execution time Memory
203206 2020-02-19T19:58:49 Z maruii Teoretičar (COCI18_teoreticar) C++14
130 / 130
 4743 ms 63968 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 9 ms 5112 KB Output is correct
4 Correct 8 ms 5116 KB Output is correct
5 Correct 8 ms 5112 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Correct 8 ms 5112 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 8 ms 5112 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5496 KB Output is correct
2 Correct 12 ms 5496 KB Output is correct
3 Correct 12 ms 5664 KB Output is correct
4 Correct 10 ms 5496 KB Output is correct
5 Correct 11 ms 5624 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5496 KB Output is correct
2 Correct 12 ms 5496 KB Output is correct
3 Correct 12 ms 5752 KB Output is correct
4 Correct 10 ms 5624 KB Output is correct
5 Correct 9 ms 5368 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 700 ms 31520 KB Output is correct
2 Correct 3715 ms 52552 KB Output is correct
3 Correct 1315 ms 42516 KB Output is correct
4 Correct 689 ms 48992 KB Output is correct
5 Correct 524 ms 41324 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 31676 KB Output is correct
2 Correct 1324 ms 42628 KB Output is correct
3 Correct 1801 ms 47240 KB Output is correct
4 Correct 671 ms 47300 KB Output is correct
5 Correct 103 ms 16372 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1693 ms 37340 KB Output is correct
2 Correct 2516 ms 47720 KB Output is correct
3 Correct 94 ms 11668 KB Output is correct
4 Correct 765 ms 55432 KB Output is correct
5 Correct 180 ms 33884 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 987 ms 63968 KB Output is correct
2 Correct 4059 ms 53720 KB Output is correct
3 Correct 2252 ms 49800 KB Output is correct
4 Correct 873 ms 59368 KB Output is correct
5 Correct 674 ms 56024 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 754 ms 46600 KB Output is correct
2 Correct 4743 ms 57036 KB Output is correct
3 Correct 3090 ms 50444 KB Output is correct
4 Correct 889 ms 59112 KB Output is correct
5 Correct 744 ms 55144 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 773 ms 49384 KB Output is correct
2 Correct 4621 ms 56116 KB Output is correct
3 Correct 2458 ms 46852 KB Output is correct
4 Correct 150 ms 18652 KB Output is correct
5 Correct 863 ms 54584 KB Output is correct