#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
const int MAX_LOG = 18;
vector<pair<int, int>> a[MAXN];
vector<pair<int, int>> bridges[MAXN];
vector<pair<int, int>> edges;
int parent[MAXN][MAX_LOG];
int tin[MAXN];
int tout[MAXN];
int components = 0;
int counter = 0;
int bridge = 0;
int num[MAXN];
int low[MAXN];
bool isBridge[MAXN];
int vis[MAXN];
int comp[MAXN];
int cnt[MAXN];
int ans[MAXN];
int inv[MAXN];
int n, m, p;
void dfs(int u, int p, int f){
num[u] = low[u] = ++counter;
for (auto x: a[u]){
int v = x.first;
if (x.second == f) continue;
if (!num[v]){
dfs(v, u, x.second);
low[u] = min(low[u], low[v]);
if (low[v] == num[v]){
bridge++;
isBridge[x.second] = true;
}
}
else low[u] = min(low[u], num[v]);
}
}
void dfs1(int u, int p){
comp[u] = components;
vis[u] = 1;
for (auto v: a[u]){
if (vis[v.first] || isBridge[v.second]) continue;
dfs1(v.first, u);
}
}
void dfs2(int u, int p){
parent[u][0] = p;
tin[u] = ++counter;
for (auto x: bridges[u]){
int v = x.first;
if (v != p){
inv[x.second] = (u != comp[edges[x.second].first]);
dfs2(v, u);
}
}
tout[u] = ++counter;
}
bool Ancestor(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int LCA(int u, int v){
if (Ancestor(u, v)) return u;
if (Ancestor(v, u)) return v;
for (int k = MAX_LOG - 1; k >= 0; k--){
if (!Ancestor(parent[u][k], v)){
u = parent[u][k];
}
}
return parent[u][0];
}
void pre(){
counter = 0;
dfs2(1, 1);
for (int k = 1; k < MAX_LOG; k++){
for (int i = 1; i <= components; i++){
parent[i][k] = parent[parent[i][k - 1]][k - 1];
}
}
}
void dfs3(int u, int p){
for (auto x: bridges[u]){
int v = x.first;
if (v == p) continue;
dfs3(v, u);
cnt[u] += cnt[v];
if (cnt[v] > 0){
ans[x.second] = 1;
}
else if (cnt[v] < 0){
ans[x.second] = -1;
}
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++){
int x, y;
cin >> x >> y;
a[x].push_back({y, i});
a[y].push_back({x, i});
edges.push_back({x, y});
}
counter = 0;
for (int i = 1; i <= n; i++){
if (!num[i]){
dfs(1, -1, -1);
}
}
for (int i = 1; i <= n; i++){
if (!vis[i]){
components++;
dfs1(i, -1);
}
}
for (int i = 0; i < m; i++){
if (isBridge[i]){
bridges[comp[edges[i].first]].push_back({comp[edges[i].second], i});
bridges[comp[edges[i].second]].push_back({comp[edges[i].first], i});
}
}
pre();
cin >> p;
while (p--){
int x, y;
cin >> x >> y;
x = comp[x];
y = comp[y];
int lca = LCA(x, y);
cnt[x]++;
cnt[y]--;
cnt[lca] += 0;
}
dfs3(1, -1);
for (int i = 0; i < m; i++){
if (inv[i]) ans[i] *= (-1);
if (ans[i] == -1) cout << "R";
else if (ans[i] == 1) cout << "L";
else cout << "B";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
4952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
