QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408655#3487. Tree Hugginge3c8f1a924RE 2ms11912kbC++142.2kb2024-05-10 20:48:252024-05-10 20:48:27

Judging History

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

  • [2024-05-10 20:48:27]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:11912kb
  • [2024-05-10 20:48:25]
  • 提交

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;
		for (int v : e[u]) {
			if (f[v]) continue; f[v] = u;
			for (int w : re[v]) if (!vis[w]) q.push(w);
		}
	}
}
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 {
			assert(n < 1000 || c == 2);
			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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 10840kb

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

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: