QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408675#3487. Tree Hugginge3c8f1a924RE 0ms8292kbC++142.2kb2024-05-10 21:06:152024-05-10 21:06:17

Judging History

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

  • [2024-05-10 21:06:17]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:8292kb
  • [2024-05-10 21:06:15]
  • 提交

answer

#include<iostream>
#include<vector>
#include<queue>
#include<cassert>
std::vector<int> e[100005], re[100005];
int n, f[100005], U[200005], V[200005], w[100005], d[100005];
int vis[100005];
void getW(int u) {
	static int vis[100005];
	for (int v : e[u]) {
		if (vis[v] != u) vis[v] = u, w[u]++;
	}
}
void bfs(int u) {
	static std::queue<int> q; q.push(u);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		if (vis[u]) continue; vis[u] = 1;
		int c = 0;
		for (int v : e[u]) {
			if (f[v]) continue; f[v] = u, c++;
			for (int w : re[v]) if (!vis[w]) q.push(w);
		}
		assert(n < 1000 || c + 1 == e[u].size());
	}
}
void build(int u) {
	static int occ[100005];
	static std::queue<int> q;
	while (!q.empty()) q.pop();
	q.push(u);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		if (vis[u]) continue;
		int c = 0;
		for (int v : e[u]) if (occ[v]) c++;
		if (c <= 1) {
			vis[u] = 1;
			for (int v : e[u]) {
				occ[v] = 1;
				for (int w : re[v]) if (!vis[w]) q.push(w);
			}
		} else {
			for (int v : e[u]) {
				if (!occ[v]) continue; f[v] = u;
				static std::queue<int> Q;
				for (int w : re[v]) if (vis[w] == 1) Q.push(w);
				while (!Q.empty()) {
					int u = Q.front(); Q.pop();
					if (vis[u] != 1) continue;
					vis[u] = -1;
					for (int v : e[u]) {
						if (f[v]) continue; f[v] = u;
						for (int w : re[v]) if (vis[w] == 1) Q.push(w);
					}
				}
				bfs(u);
				return;
			}
		}
	}
}
int ans[200005], g[100005];
int main() {
	std::cin >> n;
	for (int i = 1; i <= 2 * (n - 1); i++) {
		std::cin >> U[i] >> V[i];
		e[U[i]].push_back(V[i]), re[V[i]].push_back(U[i]);
	}
	for (int i = 1; i < n; i++) getW(i), d[i] = e[i].size();
	for (int i = 1; i < n; i++) {
		if (vis[i] || w[i] != d[i] - 1) continue;
		bfs(i);
	}
	for (int i = 1; i < n; i++) if (!vis[i]) build(i);
	for (int i = 2; i <= n; i++) if (!f[i]) return std::cout << "impossible\n", 0;
	for (int i = 1; i <= 2 * (n - 1); i++) {
		int u = U[i], v = V[i];
		if (f[v] == u) ans[i] = 1, f[v] = 0;
		else if (g[u]) return std::cout << "impossible\n", 0;
		else g[u] = v;
	}
	for (int i = 1; i <= 2 * (n - 1); i++) std::cout << (ans[i] ? 'L' : 'R');
	std::cout << std::endl;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 8292kb

input:

5
1 2
2 5
2 3
1 3
3 5
4 5
3 4
1 3

output:

LLRLRRLR

result:

ok 

Test #2:

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

input:

3
1 2
1 2
1 3
1 3

output:

impossible

result:

ok 

Test #3:

score: -100
Runtime Error

input:

100000
47469 47470
72550 72551
31535 81534
49832 99831
86776 86777
12769 12770
39146 89145
14425 14426
35647 85646
90570 90571
77055 77056
30465 80465
82785 82786
88530 88531
50015 50016
96964 96965
45984 45985
47158 97158
98106 98107
1818 51817
31919 81919
25944 75943
17755 17756
26979 76978
56457 ...

output:


result: