QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#470253 | #895. Color | qL | WA | 1ms | 4120kb | C++23 | 3.2kb | 2024-07-10 11:36:09 | 2024-07-10 11:36:09 |
Judging History
answer
#include <algorithm>
#include <cstdio>
using i32 = int;
constexpr i32 N = 200;
i32 n, m, mat[N + 1][N + 1], col[N + 1][N + 1];
i32 set0[N + 1], set1[N + 1], set2[N + 1];
struct {
i32 ver, nxt, cap;
} edge[N * N];
i32 head[N * 2 + 5], cur[N * 2 + 5], etot;
i32 S, T;
void Init() noexcept { __builtin_memset(head, etot = -1, sizeof(head)); }
void add(i32 u, i32 v, i32 f) noexcept { edge[++etot] = {v, head[u], f}, head[u] = etot; }
void link(i32 u, i32 v, i32 f) noexcept { add(u, v, f), add(v, u, 0); }
i32 dep[N * 2 + 5];
bool bfs() noexcept {
static i32 que[N * 2 + 5], *hd, *tl;
__builtin_memcpy(cur, head, sizeof(cur));
__builtin_memset(dep, -1, sizeof(dep));
dep[*(hd = tl = que) = S] = 0;
for (i32 u; hd <= tl;)
for (i32 e = head[u = *hd++], v; ~e; e = edge[e].nxt)
if (edge[e].cap && !~dep[v = edge[e].ver]) dep[ *++tl = v] = dep[u] + 1;
return ~dep[T];
}
i32 dfs(i32 u, i32 flow) noexcept {
if (u == T || !flow) return flow;
i32 rest = flow, cap;
for (i32 &e = cur[u], v; ~e && rest; e = edge[e].nxt)
if (edge[e].cap && dep[v = edge[e].ver] == dep[u] + 1)
cap = dfs(v, std::min(rest, edge[e].cap)), edge[e].cap -= cap, edge[e ^ 1].cap += cap, rest -= cap;
return flow - rest;
}
i32 Dinic() noexcept {
i32 flow = 0;
while (bfs())
for (i32 cap; cap = dfs(S, 0x3f3f3f3f), cap;) flow += cap;
return flow;
}
i32 eid[N + 1][N + 1];
signed main() noexcept {
scanf("%d%d", &n, &m), S = 0, T = m * 2 + 1;
if (!(m & 1)) return puts("No"), 0;
for (i32 i = 1; i < n; ++i)
for (i32 j = i + 1; j <= n; ++j)
scanf("%d", &mat[i][j]), ++set2[mat[j][i] = mat[i][j]], ++col[i][mat[i][j]], ++col[j][mat[i][j]];
for (i32 i = 1; i <= n; ++i)
for (i32 j = 1; j <= m; ++j)
if (col[i][j] > 1)
return puts("No"), 0;
else if (!col[i][j])
++set1[j];
for (i32 j = 1; j <= m; ++j)
if (set0[j] = (m + 1) / 2 - set1[j] - set2[j], set0[j] < 0) return puts("No"), 0;
for (; n <= m;) {
Init();
for (i32 i = 1; i <= m; ++i) link(S, i, 1), link(i + m, T, 1);
for (i32 i = 1; i <= n; ++i)
for (i32 j = 1; j <= m; ++j)
if (!col[i][j]) link(j, i + m, 1), eid[i][j] = etot;
i32 cur = 0;
for (i32 i = 1; i <= m; ++i)
for (i32 k = 1; k <= 2 * set0[i]; ++k) link(i, m + n + (++cur), 1);
i32 flow = Dinic();
// if (flow != m) {
// puts("No");
// return 0;
// }
for (i32 i = 1; i <= n; ++i)
for (i32 j = 1; j <= m; ++j)
if (!col[i][j]) {
if (edge[eid[i][j]].cap) {
mat[i][n + 1] = mat[n + 1][i] = j;
}
}
++n;
__builtin_memset(col, 0, sizeof(col));
__builtin_memset(set0, 0, sizeof(set0));
__builtin_memset(set1, 0, sizeof(set1));
__builtin_memset(set2, 0, sizeof(set2));
for (i32 i = 1; i < n; ++i)
for (i32 j = i + 1; j <= n; ++j) ++set2[mat[j][i] = mat[i][j]], ++col[i][mat[i][j]], ++col[j][mat[i][j]];
for (i32 i = 1; i <= n; ++i)
for (i32 j = 1; j <= m; ++j)
if (col[i][j] > 1)
return puts("No"), 0;
else if (!col[i][j])
++set1[j];
for (i32 j = 1; j <= m; ++j)
if (set0[j] = (m + 1) / 2 - set1[j] - set2[j], set0[j] < 0) return puts("No"), 0;
}
puts("Yes");
for (i32 i = 1; i <= m + 1; ++i, puts(""))
for (i32 j = i + 1; j <= m + 1; ++j) printf("%d ", mat[i][j]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4120kb
input:
3 5 1 2 4
output:
Yes 1 2 4 3 5 4 3 5 2 5 1 3 2 1 4
result:
ok ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
4 5 1 2 3 3 2 1
output:
No
result:
ok ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
9 11 11 10 3 4 7 5 2 8 2 10 7 4 6 5 1 9 6 3 8 4 11 5 11 2 6 7 10 3 9 2 9 8 5 1 10 3
output:
No
result:
ok ok
Test #4:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
12 11 2 11 8 9 1 3 10 7 5 4 6 5 11 10 6 4 9 8 7 1 3 3 8 4 9 7 2 10 6 1 5 2 6 1 4 9 10 7 11 2 6 3 1 7 4 7 8 10 3 9 5 5 1 8 11 10 11 4 3 2 6 5 9 2 11 8
output:
Yes 2 11 8 9 1 3 10 7 5 4 6 5 11 10 6 4 9 8 7 1 3 3 8 4 9 7 2 10 6 1 5 2 6 1 4 9 10 7 11 2 6 3 1 7 4 7 8 10 3 9 5 5 1 8 11 10 11 4 3 2 6 5 9 2 11 8
result:
ok ok
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3972kb
input:
3 9 2 8 4
output:
No
result:
wrong answer Jury has the answer but participant has not