#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define LL long long
#define LD long double
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, j, n) for(int i = j; i <= n; ++i)
#define boost cin.tie(0), ios_base::sync_with_stdio(0);
using namespace std;
const int nax = 4e5 + 111;
int L, R, m;
int a, b;
struct gao {
int a, b, id;
};
vector <gao> x;
vector <gao> tyt;
int n;
int color = 1;
vector <pair<int, int>> v[nax];
int deg[nax];
int ans[nax];
bool odw[nax];
int wsk[nax];
void dfs(int u, int par = 0, int p = -1, int id = -1) {
while (wsk[u] < ss(v[u])) {
pair<int, int> it = v[u][wsk[u]];
wsk[u]++;
if (odw[it.se]) continue;
odw[it.se] = 1;
dfs(it.fi, (par + 1) % 2, u, it.se);
}
if (id == -1) return;
tyt.pb({min(u, p), max(u, p), id});
}
void solve(vector <gao> y) {
vector <gao> Left, Right;
for (auto &it : y)
if (it.a > it.b) swap(it.a, it.b);
for (auto it : y) {
deg[it.a]++;
deg[it.b]++;
}
int MAX = 0;
for (auto it : y) {
MAX = max(MAX, deg[it.a]);
MAX = max(MAX, deg[it.b]);
}
if (MAX == 1) {
for (auto it : y) {
ans[it.id] = color;
deg[it.a] = 0;
deg[it.b] = 0;
}
color++;
return;
}
int nowe = m + 1;
for (auto it : y) {
v[it.a].pb({it.b, it.id});
v[it.b].pb({it.a, it.id});
}
for (auto it : y) {
if (ss(v[it.a]) % 2 == 1) {
v[it.a].pb({n + 1, nowe});
v[n + 1].pb({it.a, nowe++});
}
if (ss(v[it.b]) % 2 == 1) {
v[it.b].pb({n + 2, nowe});
v[n + 2].pb({it.b, nowe++});
}
}
if (ss(v[n + 1]) % 2 == 1) {
v[n + 1].pb({n + 2, nowe});
v[n + 2].pb({n + 1, nowe++});
}
assert(ss(v[n + 1]) % 2 == 0);
assert(ss(v[n + 2]) % 2 == 0);
Left.clear();
Right.clear();
tyt.clear();
for (auto it : y) {
dfs(it.a);
dfs(it.b);
}
dfs(n + 1);
dfs(n + 2);
for (int i = 0; i < ss(tyt); ++i) {
if (tyt[i].b > n) continue;
if (i & 1) Left.pb(tyt[i]);
else Right.pb(tyt[i]);
}
/*cat(ss(y));
for (auto it : y) {
cat(it.a);
cat(it.b);
cat(it.id);
printf ("\n");
}
printf ("\n");
cat("L");
for (auto it : Left)
printf ("%d %d\n", it.a, it.b);
cat("R");
for (auto it : Right)
printf ("%d %d\n", it.a, it.b);
printf ("\n\n");
*/
assert(ss(Left) > 0);
assert(ss(Right) > 0);
for (auto it : y) {
v[it.a].clear();
v[it.b].clear();
wsk[it.a] = 0;
wsk[it.b] = 0;
deg[it.a] = 0;
deg[it.b] = 0;
odw[it.id] = 0;
}
v[n + 1].clear();
v[n + 2].clear();
wsk[n + 1] = 0;
wsk[n + 2] = 0;
for (int i = m + 1; i <= nowe; ++i)
odw[i] = 0;
solve(Left);
solve(Right);
}
int main() {
scanf ("%d %d %d", &L, &R, &m);
n = L + R;
for (int i = 1; i <= m; ++i) {
scanf ("%d%d", &a, &b);
b += L;
x.pb({a, b, i});
}
solve(x);
printf ("%d\n", color - 1);
for (int i = 1; i <= m; ++i)
printf ("%d\n", ans[i]);
return 0;
}
Compilation message
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d %d", &L, &R, &m);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:168:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &a, &b);
~~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9720 KB |
Output is correct |
2 |
Correct |
12 ms |
9848 KB |
Output is correct |
3 |
Correct |
12 ms |
9848 KB |
Output is correct |
4 |
Correct |
11 ms |
9720 KB |
Output is correct |
5 |
Correct |
12 ms |
9720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
9720 KB |
Output is correct |
2 |
Correct |
11 ms |
9720 KB |
Output is correct |
3 |
Correct |
11 ms |
9696 KB |
Output is correct |
4 |
Correct |
11 ms |
9720 KB |
Output is correct |
5 |
Correct |
11 ms |
9720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
11128 KB |
Output is correct |
2 |
Correct |
16 ms |
11000 KB |
Output is correct |
3 |
Correct |
20 ms |
11344 KB |
Output is correct |
4 |
Correct |
14 ms |
10584 KB |
Output is correct |
5 |
Correct |
14 ms |
10488 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
11000 KB |
Output is correct |
2 |
Correct |
17 ms |
11100 KB |
Output is correct |
3 |
Correct |
19 ms |
11496 KB |
Output is correct |
4 |
Correct |
16 ms |
10864 KB |
Output is correct |
5 |
Correct |
14 ms |
10360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
786 ms |
84088 KB |
Output is correct |
2 |
Incorrect |
4465 ms |
129012 KB |
Integer 0 violates the range [1, 2178] |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
844 ms |
84124 KB |
Output is correct |
2 |
Incorrect |
2808 ms |
126944 KB |
Integer 0 violates the range [1, 56] |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2446 ms |
113604 KB |
Integer 0 violates the range [1, 65542] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1109 ms |
106108 KB |
Integer 0 violates the range [1, 933] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
865 ms |
86616 KB |
Integer 0 violates the range [1, 4149] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
867 ms |
86756 KB |
Integer 0 violates the range [1, 4166] |
2 |
Halted |
0 ms |
0 KB |
- |