QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#408644 | #3487. Tree Hugging | e3c8f1a924 | WA | 99ms | 17432kb | C++14 | 2.2kb | 2024-05-10 20:36:49 | 2024-05-10 20:36:50 |
Judging History
answer
#include<iostream>
#include<vector>
#include<queue>
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] || w[i] != d[i]) continue;
}
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: 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: 2ms
memory: 8396kb
input:
3 1 2 1 2 1 3 1 3
output:
impossible
result:
ok
Test #3:
score: -100
Wrong Answer
time: 99ms
memory: 17432kb
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:
impossible
result:
wrong answer 'impossible' claimed, but there is a solution