QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408669 | #3487. Tree Hugging | e3c8f1a924 | RE | 112ms | 19684kb | C++14 | 2.1kb | 2024-05-10 20:57:47 | 2024-05-10 20:57:48 |
Judging History
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", (n > 1000);
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: 3ms
memory: 8300kb
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: 8296kb
input:
3 1 2 1 2 1 3 1 3
output:
impossible
result:
ok
Test #3:
score: 0
Accepted
time: 109ms
memory: 19584kb
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: 101ms
memory: 19572kb
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: 112ms
memory: 19684kb
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
Runtime Error
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