QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408662#3487. Tree Hugginge3c8f1a924WA 119ms19552kbC++142.1kb2024-05-10 20:54:012024-05-10 20:55:16

Judging History

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

  • [2024-05-10 20:55:16]
  • 评测
  • 测评结果:WA
  • 用时:119ms
  • 内存:19552kb
  • [2024-05-10 20:54:01]
  • 提交

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 {
			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: 8236kb

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

input:

3
1 2
1 2
1 3
1 3

output:

impossible

result:

ok 

Test #3:

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

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:

LRRRRLRLRRRLRRRRLLRRLRLRRRRLLRRRRLLRRLLRRLRRRLLRLLLRLRLLLRLLRRRRRRRRRRLRRLLLRLLRRRLRLLLLRRRRLLLRRRLLRRLRRRLLRRRRLLLLRRLRRLLLLLLLLRRLRLRRLLLRRLLLRRRLRRLRLLRLRRRLRRRRLRLRLRLRRLRLLRRRRRRLRLRRRRRLRRRRRLLLRRLLLRLLRLRLRLLRLLLLRLRLRLLRLLLRRLRRRLRRRRLLLRLLLRLLRRLRRLRLLLRLRRRRLRLRRLRRRRRRRLRRLRRRLLLRLRLLLLLR...

result:

ok 

Test #4:

score: 0
Accepted
time: 119ms
memory: 19540kb

input:

100000
1076 1077
2943 97058
45917 54085
42045 57957
27241 27242
23988 76014
15779 15780
64542 64543
32281 67721
1554 98448
27238 72764
35657 35658
7930 7931
47944 52058
49192 50810
20775 20776
15387 84615
57245 57246
6502 6503
41974 58028
65744 65745
8014 91987
42101 42102
18676 81326
41951 58050
26...

output:

LLRRLRLRRRRLLRRLRRLRRLLRLLRLLRLRLRLLRLLRRRRLLLLRLRRRRLRLLLRRRRLLLLRLLLRRLRLRLRLRLRRRRLRRLRLRLLRRRLRLLRRLRRLRLRRLRLRLLRLLLRLLRRRLRRRLRLLRLRRRLRRRRRRLLRRRLLRLLLRRLRLRRLRLLLLRRLRRRRLLRLRRRLRRRLLLRRRLRRLRRRRRRLRLLRRRRRLLRLLLLRRRRRLRRRRRRRLRLRRLLRLLLRRLRLRLLRLLLRRRLRRLLRLRRLRLRRRLLRLRLRRRRRRRLLRLRLLRRLLR...

result:

ok 

Test #5:

score: 0
Accepted
time: 98ms
memory: 19552kb

input:

100000
77675 77677
69316 69317
34082 34084
98715 98717
86710 86711
45509 45510
60814 60815
3829 3830
95894 95896
42710 42711
84428 84429
24015 24017
94638 94640
61396 61397
25642 25643
68450 68451
75513 75515
73310 73311
31526 31527
82360 82361
81399 81401
17066 17067
71709 71710
635 636
77378 77380...

output:

RLRRLLLLRLLRRLLLRLLLRLLLRRRRRRRLLLLLLRLLRLRRLRLLLLRLLRRRRLRRLLLLLRLLRRRRRRRRRLLRRLLLRLRRLRLLLLRRLLLLLRLLRLRLLLLRLLRLLRRRRRLRLLRRLLLRRRRRLRRRRRRRRRLLRLLRRRRLLLLLRRRLRLRLLLRRRLLLLLLLRRLLLRLLLRRLLRLRRRRRLRRLRLRLRLRLRRLRRLRLRRLLLLRLRRLLRRLLRRRRRRRRRLLLLRRLRLLLLRRRLRLLRLRRRRLLLRLLLLLLLRLRLLLLRLLLRRLRRRRR...

result:

ok 

Test #6:

score: -100
Wrong Answer
time: 101ms
memory: 18388kb

input:

100000
96292 96307
98393 98394
14849 14974
503 1000
4787 4788
42163 42164
47430 47874
2477 9905
33783 45478
29141 29191
46228 46229
48667 48668
32799 34015
34688 34689
22354 22355
4489 44498
19925 25001
47669 66799
86848 86891
92079 92867
39864 39868
14528 14529
7424 55462
78879 78885
12790 12795
62...

output:

impossible

result:

wrong answer 'impossible' claimed, but there is a solution