#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;
}
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |
# |
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 |