QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408671#3487. Tree Hugginge3c8f1a924RE 3ms8276kbC++142.2kb2024-05-10 21:00:112024-05-10 21:00:12

Judging History

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

  • [2024-05-10 21:00:12]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:8276kb
  • [2024-05-10 21:00:11]
  • 提交

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", 1;
	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", 1;
		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: 3ms
memory: 8276kb

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: -100
Runtime Error

input:

3
1 2
1 2
1 3
1 3

output:

impossible

result: