QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#470251#895. ColorqLWA 0ms4132kbC++233.2kb2024-07-10 11:35:302024-07-10 11:35:31

Judging History

你现在查看的是最新测评结果

  • [2024-07-10 11:35:31]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4132kb
  • [2024-07-10 11:35:30]
  • 提交

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: 0ms
memory: 4132kb

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: 3808kb

input:

4 5
1 2 3
3 2
1

output:

No

result:

ok ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 3800kb

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: 3936kb

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: 3748kb

input:

3 9
2 8
4

output:


result:

wrong answer The first line should be "Yes" or "No"