#include <stdio.h>
#include <stdlib.h>
#define N 200000
#define M 500000
int max(int a, int b) { return a > b ? a : b; }
int ii[M], jj[M], cc[M];
int *eh[N], eo[N], dd[N];
void dfs(int i) {
int c = 1;
while (eo[i]) {
int h = eh[i][--eo[i]], j = i ^ ii[h] ^ jj[h];
if (!cc[h])
cc[h] = c ^= 3, dd[i]--, dd[j]--, i = j;
}
}
void solve(int *hh, int m, int a, int b) {
int mid, h, h_, h1, h2, i, j, tmp;
if (m == 0)
return;
if (b - a == 1) {
for (h = 0; h < m; h++)
cc[hh[h]] = a;
return;
}
mid = (a + b) / 2;
for (h = 0; h < m; h++) {
h_ = hh[h], i = ii[h_], j = jj[h_];
eh[i][eo[i]++] = h_, eh[j][eo[j]++] = h_;
dd[i]++, dd[j]++;
}
for (h = 0; h < m; h++) {
h_ = hh[h], i = ii[h_], j = jj[h_];
if (dd[i] % 2 == 1)
dfs(i);
if (dd[j] % 2 == 1)
dfs(j);
}
for (h = 0; h < m; h++) {
h_ = hh[h], i = ii[h_], j = jj[h_];
if (dd[i] % 2 == 0)
dfs(i);
if (dd[j] % 2 == 0)
dfs(j);
}
h1 = 0, h2 = m;
while (h1 < h2) {
int c = cc[hh[h1]];
cc[hh[h1]] = 0;
if (c == 1)
h1++;
else {
h2--;
tmp = hh[h1], hh[h1] = hh[h2], hh[h2] = tmp;
}
}
solve(hh, h1, a, mid), solve(hh + h1, m - h1, mid, b);
}
int main() {
static int hh[M];
int n, n1, n2, m, h, i, j, d_;
scanf("%d%d%d", &n1, &n2, &m), n = n1 + n2;
for (h = 0; h < m; h++) {
scanf("%d%d", &i, &j), i--, j--, j += n1;
ii[h] = i, jj[h] = j;
dd[i]++, dd[j]++;
}
d_ = 0;
for (i = 0; i < n; i++) {
eh[i] = (int *) malloc(dd[i] * sizeof *eh[i]);
d_ = max(d_, dd[i]), dd[i] = 0;
}
while ((d_ & d_ - 1) != 0)
d_++;
for (h = 0; h < m; h++)
hh[h] = h;
solve(hh, m, 1, d_ + 1);
printf("%d\n", d_);
for (h = 0; h < m; h++)
printf("%d\n", cc[h]);
return 0;
}
Compilation message
teoreticar.c: In function 'main':
teoreticar.c:83:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
83 | while ((d_ & d_ - 1) != 0)
| ~~~^~~
teoreticar.c:72:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d%d%d", &n1, &n2, &m), n = n1 + n2;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.c:74:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d%d", &i, &j), i--, j--, j += n1;
| ^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
588 KB |
Output is correct |
2 |
Correct |
3 ms |
544 KB |
Output is correct |
3 |
Correct |
5 ms |
788 KB |
Output is correct |
4 |
Correct |
2 ms |
460 KB |
Output is correct |
5 |
Correct |
3 ms |
424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
460 KB |
Output is correct |
3 |
Correct |
4 ms |
844 KB |
Output is correct |
4 |
Correct |
3 ms |
460 KB |
Output is correct |
5 |
Correct |
2 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
412 ms |
15776 KB |
Output is correct |
2 |
Correct |
2394 ms |
26320 KB |
Output is correct |
3 |
Correct |
805 ms |
25000 KB |
Output is correct |
4 |
Correct |
361 ms |
21276 KB |
Output is correct |
5 |
Correct |
403 ms |
13156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
375 ms |
15748 KB |
Output is correct |
2 |
Correct |
741 ms |
24944 KB |
Output is correct |
3 |
Correct |
1294 ms |
26140 KB |
Output is correct |
4 |
Correct |
341 ms |
21308 KB |
Output is correct |
5 |
Correct |
81 ms |
3908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
999 ms |
17940 KB |
Output is correct |
2 |
Correct |
1350 ms |
19816 KB |
Output is correct |
3 |
Correct |
70 ms |
11208 KB |
Output is correct |
4 |
Correct |
647 ms |
16604 KB |
Output is correct |
5 |
Correct |
116 ms |
15480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
734 ms |
13876 KB |
Output is correct |
2 |
Correct |
2128 ms |
26564 KB |
Output is correct |
3 |
Correct |
1356 ms |
26020 KB |
Output is correct |
4 |
Correct |
530 ms |
19928 KB |
Output is correct |
5 |
Correct |
370 ms |
21404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
569 ms |
11608 KB |
Output is correct |
2 |
Correct |
2531 ms |
26776 KB |
Output is correct |
3 |
Correct |
1749 ms |
25976 KB |
Output is correct |
4 |
Correct |
565 ms |
19780 KB |
Output is correct |
5 |
Correct |
555 ms |
16196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
568 ms |
11628 KB |
Output is correct |
2 |
Correct |
2530 ms |
26700 KB |
Output is correct |
3 |
Correct |
1313 ms |
25512 KB |
Output is correct |
4 |
Correct |
109 ms |
4420 KB |
Output is correct |
5 |
Correct |
659 ms |
16040 KB |
Output is correct |