QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#408671 | #3487. Tree Hugging | e3c8f1a924 | RE | 3ms | 8276kb | C++14 | 2.2kb | 2024-05-10 21:00:11 | 2024-05-10 21:00:12 |
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 {
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;
}
詳細信息
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