#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];
int c;
void dfs(int i) {
while (eo[i]) {
int h = eh[i][--eo[i]];
if (cc[h] == 0)
cc[h] = -1, dfs(i ^ ii[h] ^ jj[h]), cc[h] = c ^= 3;
}
}
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_;
}
c = 2;
for (h = 0; h < m; h++) {
h_ = hh[h], i = ii[h_], j = jj[h_];
if (eo[i] % 2 == 1)
dfs(i);
if (eo[j] % 2 == 1)
dfs(j);
}
for (h = 0; h < m; h++) {
h_ = hh[h], i = ii[h_], j = jj[h_];
if (eo[i] % 2 == 0)
dfs(i);
if (eo[j] % 2 == 0)
dfs(j);
}
h1 = 0, h2 = m;
while (h1 < h2) {
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], cc_[M + 1];
int n, n1, n2, m, h, i, j, d_, c;
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;
eo[i]++, eo[j]++;
}
d_ = 0;
for (i = 0; i < n; i++) {
eh[i] = (int *) malloc(eo[i] * sizeof *eh[i]);
d_ = max(d_, eo[i]);
eo[i] = 0;
}
while ((d_ & d_ - 1) != 0)
d_++;
for (h = 0; h < m; h++)
hh[h] = h;
solve(hh, m, 1, d_ + 1);
for (h = 0, c = 0; h < m; h++) {
if (!cc_[cc[h]])
cc_[cc[h]] = ++c;
cc[h] = cc_[cc[h]];
}
printf("%d\n", c);
for (h = 0; h < m; h++)
printf("%d\n", cc[h]);
return 0;
}
Compilation message
teoreticar.c: In function 'main':
teoreticar.c:82:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
82 | while ((d_ & d_ - 1) != 0)
| ~~~^~~
teoreticar.c:70:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d%d%d", &n1, &n2, &m), n = n1 + n2;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.c:72:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d%d", &i, &j), i--, j--, j += n1;
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
332 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
0 ms |
332 KB |
Output is correct |
| 5 |
Correct |
0 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
716 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
844 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
716 KB |
not colored properly |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
390 ms |
30204 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
399 ms |
30180 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1168 ms |
45932 KB |
Output is correct |
| 2 |
Incorrect |
1318 ms |
42856 KB |
not colored properly |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
896 ms |
45124 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
639 ms |
36612 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
731 ms |
36624 KB |
not colored properly |
| 2 |
Halted |
0 ms |
0 KB |
- |
