이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
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;
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);
printf("%d\n", d_);
for (h = 0; h < m; h++)
printf("%d\n", cc[h]);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |