QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#511412#5504. Flower GardenqLWA 1805ms161032kbC++144.2kb2024-08-09 20:47:242024-08-09 20:47:24

Judging History

This is the latest submission verdict.

  • [2024-08-09 20:47:24]
  • Judged
  • Verdict: WA
  • Time: 1805ms
  • Memory: 161032kb
  • [2024-08-09 20:47:24]
  • Submitted

answer

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <vector>
using i32 = int;
using i64 = long long;
constexpr i32 N = 1E5;
i32 n, m, s;
std::vector<i32> G[N * 9];
struct {
	i32 id1, id2;
} tr[N * 4];
i32 id, in[N + 1], out[N + 1], val[N * 9];
void build(i32 p, i32 l, i32 r) noexcept {
	tr[p].id1 = ++id, tr[p].id2 = ++id;
	if (l == r) return in[l] = tr[p].id1, val[out[r] = tr[p].id2] = 1, void(G[in[l]].emplace_back(out[r]));
	i32 mid = (l + r) >> 1;
	build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
	G[tr[p].id1].emplace_back(tr[p << 1].id1), G[tr[p].id1].emplace_back(tr[p << 1 | 1].id1);
	G[tr[p << 1].id2].emplace_back(tr[p].id2), G[tr[p << 1 | 1].id2].emplace_back(tr[p].id2);
}
template <typename Linker>
void link(i32 p, i32 l, i32 r, i32 L, i32 R, Linker&& linker) noexcept {
	if (L <= l && r <= R) return linker(tr[p].id1, tr[p].id2);
	i32 mid = (l + r) >> 1;
	if (L <= mid) link(p << 1, l, mid, L, R, linker);
	if (R > mid) link(p << 1 | 1, mid + 1, r, L, R, linker);
}
i32 dfn[N * 9], low[N * 9], cur;
i32 sta[N * 9], *top;
bool ins[N * 9];
i32 scc[N * 9], siz[N * 9], col;
void dfs(i32 u) noexcept {
	dfn[u] = low[u] = ++cur, ins[*++top = u] = true;
	for (i32 v : G[u])
		if (!dfn[v])
			dfs(v), low[u] = std::min(low[u], low[v]);
		else if (ins[v])
			low[u] = std::min(low[u], dfn[v]);
	if (dfn[u] == low[u]) {
		siz[++col] = 0;
		do siz[scc[*top] = col] += val[*top], ins[*top] = false;
		while (*top-- != u);
	}
}
std::vector<i32> H[N * 9], R[N * 9];
i32 deg[N * 9], seq[N * 9];
i32 que[N * 9], *hd, *tl;
char ans[N * 9];
template <std::vector<i32>* T>
i32 dfs(i32 u, std::vector<i32>& vec) noexcept {
	i32 sum = siz[u];
	for (i32 v : T[u]) sum += dfs<T>(v, vec);
	return vec.emplace_back(u), sum;
}
signed main() noexcept {
	i32 Test;
	for (scanf("%d", &Test); Test; --Test) {
		for (i32 i = 1; i <= id; ++i) G[i].clear();
		__builtin_memset(dfn + 1, 0, sizeof(i32) * id);
		__builtin_memset(low + 1, 0, sizeof(i32) * id);
		__builtin_memset(val + 1, 0, sizeof(i32) * id);
		for (i32 i = 1; i <= col; ++i) H[i].clear(), R[i].clear();
		scanf("%d%d", &n, &m), s = n, id = 0, build(1, 1, n *= 3);
		for (i32 a, b, c, d; m; --m)
			scanf("%d%d%d%d", &a, &b, &c, &d), ++id,
				link(1, 1, n, a, b, [](i32 in, i32 out) noexcept { G[out].emplace_back(id); }),
				link(1, 1, n, c, d, [](i32 in, i32 out) noexcept { G[id].emplace_back(in); });
		cur = 0, top = sta, col = 0;
		for (i32 i = 1; i <= id; ++i)
			if (!dfn[i]) dfs(i);
		for (i32 i = 1; i <= id; ++i)
			for (i32 j : G[i])
				if (scc[i] != scc[j]) H[scc[i]].emplace_back(scc[j]);
		for (i32 i = 1; i <= col; ++i)
			std::sort(H[i].begin(), H[i].end()), H[i].erase(std::unique(H[i].begin(), H[i].end()), H[i].end());
		for (i32 i = 1; i <= col; ++i)
			for (i32 j : H[i]) R[j].emplace_back(i);
		for (i32 i = 1; i <= col; ++i)
			std::sort(R[i].begin(), R[i].end()), R[i].erase(std::unique(R[i].begin(), R[i].end()), R[i].end());
		for (i32 i = 1; i <= col; ++i)
			for (i32 j : H[i]) ++deg[j];
		hd = tl = que, cur = 0;
		for (i32 i = 1; i <= col; ++i)
			if (!deg[i]) *tl++ = i;
		for (i32 u; hd != tl;)
			for (i32 v : H[seq[++cur] = u = *hd++])
				if (!--deg[v]) *tl++ = v;
		assert(cur == col);
		bool flag = false;
		for (i32 t = 1; t <= col && !flag; ++t)
			if (siz[t] >= s) {
				std::vector<i32> pv, sv;
				i32 pre = dfs<R>(t, pv), suf = dfs<H>(t, sv);
				if (pre <= s * 2) {
					__builtin_memset(ans + 1, 'F', sizeof(char) * col);
					for (i32 it : pv) ans[it] = 'R';
					puts("TAK");
					for (i32 i = 1; i <= n; ++i) putchar(ans[scc[out[i]]]);
					puts(""), flag = true;
				} else if (suf <= s * 2) {
					__builtin_memset(ans + 1, 'R', sizeof(char) * col);
					for (i32 it : sv) ans[it] = 'F';
					puts("TAK");
					for (i32 i = 1; i <= n; ++i) putchar(ans[scc[out[i]]]);
					puts(""), flag = true;
				}
			}
		if (!flag) {
			i32 sum = 0;
			__builtin_memset(ans + 1, 'F', sizeof(char) * col);
			for (i32 i = 1; i <= col && (sum += siz[seq[i]]) <= s; ++i) ans[seq[i]] = 'R';
			if (sum == n)
				puts("NIE");
			else {
				puts("TAK");
				for (i32 i = 1; i <= n; ++i) putchar(ans[scc[out[i]]]);
				puts("");
			}
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 87788kb

input:

2
1 3
1 1 2 2
1 2 3 3
1 1 3 3
1 3
1 1 2 2
2 2 3 3
3 3 1 1

output:

TAK
RRF
NIE

result:

ok good!

Test #2:

score: -100
Wrong Answer
time: 1805ms
memory: 161032kb

input:

10
33333 100000
28701 40192 93418 95143
95902 97908 78378 78461
36823 44196 22268 23996
23977 24786 33315 48829
83965 90411 4923 8445
20235 21177 32543 47454
29598 35414 72477 73049
2014 12632 42163 46466
64305 65518 98825 99552
32331 41625 92772 96224
26500 54122 76990 77126
18249 20335 31165 36080...

output:

TAK
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

result:

wrong answer zla odpowiedz!