#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct Tree{
int n, root;
vector<int> depth, head, sz, pa;
vector<int> f;
Tree(int n, int root, vector<vector<int>> &adj): n(n), root(root){
depth.resize(n+1, -1);
head.resize(n+1);
sz.resize(n+1, 0);
pa.resize(n+1, -1);
auto rootTree = [&](auto rootTree, int u, int p) -> void{
depth[u] = depth[p]+1;
pa[u] = p;
sz[u] = 1;
for(int v : adj[u]){
if(v == p) continue;
rootTree(rootTree, v, u);
sz[u] += sz[v];
}
};
rootTree(rootTree, root, 0);
auto decompose = [&](auto decompose, int u, int h) -> void{
head[u] = h;
int heavy = -1;
for(int v : adj[u]){
if(v == pa[u]) continue;
if(heavy == -1 || sz[heavy] < sz[v]) heavy = v;
}
if(heavy != -1) decompose(decompose, heavy, h);
for(int v : adj[u]){
if(v == pa[u] || v == heavy) continue;
decompose(decompose, v, v);
}
};
decompose(decompose, root, root);
f = [&]{
vector<array<int, 2>> first(n+1);
vector<array<int, 2>> second(n+1);
function<void(int, int)> dfs0 = [&](int u, int p) {
first[u] = second[u] = {0, -1};
for (int v : adj[u]) {
if (v == p) {
continue;
}
dfs0(v, u);
auto fetch = first[v];
fetch[0] += 1;
fetch[1] = v;
if (fetch > first[u]) {
swap(fetch, first[u]);
}
if (fetch > second[u]) {
swap(fetch, second[u]);
}
}
};
dfs0(1, 0);
function<void(int, int)> dfs = [&](int u, int p) {
for (int v : adj[u]) {
if (v == p) {
continue;
}
auto fetch = first[u][1] == v ? second[u] : first[u];
fetch[0] += 1;
fetch[1] = u;
if (fetch > first[v]) {
swap(fetch, first[v]);
}
if (fetch > second[v]) {
swap(fetch, second[v]);
}
dfs(v, u);
}
};
dfs(1, 0);
vector<int> f(n+1);
for (int u = 1; u <= n; u++) {
f[u] = first[u][0];
}
return f;
}();
};
int lca(int u, int v){
for(; head[u] != head[v]; v = pa[head[v]]){
if(depth[head[u]] > depth[head[v]]) swap(u, v);
}
if(depth[u] > depth[v]) swap(u, v);
return u;
}
int dist(int u, int v) {
return depth[u]+depth[v]-2*depth[lca(u, v)];
}
};
struct path{
int u, v, lca;
};
struct edge{
int v, id, val;
};
struct edg{
int u, v;
};
void BridgeTree(int n, vector<vector<edge>> adj, vector<vector<edge>> &tree, vector<int> &comp, vector<int> &bridge){
vector<int> tin(n+1), low(n+1), stk;
vector<bool> vis(n+1, 0);
fill(comp.begin(), comp.end(), -1);
tree.emplace_back();
int timer = 0, id = 0;
auto dfs = [&](auto dfs, int u, int p) -> void{
vis[u] = true;
stk.push_back(u);
timer++;
low[u] = tin[u] = timer;
bool skipped = false;
for(auto it : adj[u]){
int v = it.v;
if(v == p && !skipped){
skipped = true;
continue;
}
if(vis[v]){
low[u] = min(low[u], tin[v]);
}else{
dfs(dfs, v, u);
low[u] = min(low[u], low[v]);
}
}
if(low[u] == tin[u]){
int v;
id++;
tree.emplace_back();
do{
v = stk.back();
stk.pop_back();
comp[v] = id;
for(auto it : adj[v]) {
int w = it.v, id = it.id;
if(comp[w] != -1 && comp[w] != comp[v]){
bridge.push_back(id);
tree[comp[w]].push_back({comp[v], id});
tree[comp[v]].push_back({comp[w], id});
}
}
}while(v != u);
}
};
dfs(dfs, 1, 0);
}
void solve(){
int n, m;
cin >> n >> m;
vector<vector<edge>> adj(n+1);
vector<edg> e(m+1);
for(int i = 1; i <= m; i++){
int u, v;
cin >> u >> v;
e[i] = {u, v};
adj[u].push_back({v, i});
adj[v].push_back({u, i});
}
//bridge tree
vector<vector<edge>> tree;
vector<int> comp(n+1, -1), bridge;
BridgeTree(n, adj, tree, comp, bridge);
int N = tree.size()-1;
vector<vector<int>> tree2(N+1);
for(int i = 1; i <= N; i++){
for(auto it : tree[i]){
int j = it.v;
tree2[i].push_back(j);
}
}
Tree Y(n, 1, tree2);
int p;
cin >> p;
vector<path> pth(p+1);
for(int i = 1; i <= p; i++){
cin >> pth[i].u >> pth[i].v;
pth[i].u = comp[pth[i].u];
pth[i].v = comp[pth[i].v];
pth[i].lca = Y.lca(pth[i].u, pth[i].v);
}
sort(pth.begin()+1, pth.end(), [&](path a, path b){return Y.depth[a.lca] < Y.depth[b.lca];});
vector<edge> pa(N+1, {0, 0, 0});
auto dfs = [&](auto dfs, int u, int p) -> void{
for(auto it : tree[u]){
int v = it.v, id = it.id;
if(v == p) continue;
pa[v] = {u, id, 0};
dfs(dfs, v, u);
}
};
dfs(dfs, 1, 0);
vector<int> ud(m+1, 0);
for(int i = 1; i <= p; i++){
int u = pth[i].u, v = pth[i].v;
while(u != pth[i].lca && pa[u].val == 0){
ud[pa[u].id] = 1;
pa[u].val = 1;
u = pa[u].v;
}
while(v != pth[i].lca && pa[v].val == 0){
ud[pa[v].id] = -1;
pa[v].val = -1;
v = pa[v].v;
}
}
vector<char> ans(m+1, ' ');
vector<bool> non_bridge(m+1, true);
for(int i : bridge){
non_bridge[i] = false;
}
for(int i = 1; i <= m; i++){
if(non_bridge[i] || ud[i] == 0){
ans[i] = 'B';
}else{
if(ud[i] == -1){
if(Y.depth[comp[e[i].u]] < Y.depth[comp[e[i].v]]){
ans[i] = 'R';
}else{
ans[i] = 'L';
}
}else{
if(Y.depth[comp[e[i].u]] < Y.depth[comp[e[i].v]]){
ans[i] = 'L';
}else{
ans[i] = 'R';
}
}
}
}
for(int i = 1; i <= m; i++){
cout << ans[i];
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
