#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, LG = 20;
int d[N], a[N], b[N], in[N], out[N], dp[N], p[N][2], L[N][LG], n, m, q;
vector < int > edges[N];
bool ok[N], vis[N], marked[N][2];
map < pair < int, int >, int > ind;
void dfs(int x, int p){
static int timer = 0;
vis[x] = true;
d[x] = d[p] + 1;
L[x][0] = p;
for(int i = 1; i < LG; ++i) L[x][i] = L[L[x][i - 1]][i - 1];
in[x] = ++timer;
for(int i = 0; i < (int)edges[x].size(); ++i){
int to = edges[x][i];
if(to != p){
if(!vis[to]){
dfs(to, x);
dp[x] += dp[to];
}else{
dp[x] += in[x] < in[to] ? -1 : 1;
}
}
}
out[x] = ++timer;
ok[ind[{x, p}]] = !dp[x];
}
bool isAnc(int potAnc, int potChild){
return !potAnc || in[potAnc] <= in[potChild] && out[potAnc] >= out[potChild];
}
int lca(int u, int v){
if(isAnc(u, v))return u;
if(isAnc(v, u))return v;
for(int i = LG - 1; ~i; --i){
if(!isAnc(L[u][i], v))u = L[u][i];
}
return L[u][0];
}
int find(int x, int dist){
for(int bit = 0; bit < LG; ++bit){
if(dist >> bit & 1)x = L[x][bit];
}
return x;
}
void make_set(int x){
p[x][0] = p[x][1] = x;
marked[x][0] = marked[x][1] = 0;
}
int find_set(int x, bool TYPE){
return p[x][TYPE] == x ? x : p[x][TYPE] = find_set(p[x][TYPE], TYPE);
}
void union_sets(int a, int b, bool TYPE){
a = find_set(a, TYPE);
b = find_set(b, TYPE);
marked[a][TYPE] = marked[b][TYPE] = 1;
if(a == b)return;
if(d[a] > d[b])swap(a, b);
p[b][TYPE] = a;
}
void unite(int fr, int to, bool TYPE){
while(d[fr] >= d[to]){
int nxt = L[find_set(fr, TYPE)][0];
union_sets(fr, to, TYPE);
fr = nxt;
}
}
void directEdges(int fr, int to){
int l = lca(fr, to);
int dist1 = d[fr] - d[l];
int dist2 = d[to] - d[l];
if(dist1)unite(fr, find(fr, dist1 - 1), 0);
if(dist2)unite(to, find(to, dist2 - 1), 1);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int u, v, i = 1; i <= m; ++i){
cin >> a[i] >> b[i];
edges[a[i]].push_back(b[i]);
edges[b[i]].push_back(a[i]);
ind[{a[i], b[i]}] = ind[{b[i], a[i]}] = i;
}
for(int i = 1; i <= n; ++i)make_set(i);
dfs(1, 0);
cin >> q;
for(int u, v, i = 1; i <= q; ++i){
cin >> u >> v;
directEdges(u, v);
}
for(int i = 1; i <= m; ++i){
char direction = 'B';
if(ok[i]){
int child = a[i], parent = b[i];
bool swapped = false;
if(d[child] < d[parent])swap(parent, child), swapped = true;
int x = find_set(child, 0);
int y = find_set(child, 1);
if(marked[x][0]) direction = 'R';
if(marked[y][1]) direction = 'L';
if(swapped)direction = 'L' + 'R' - direction;
}
cout << direction;
}
}
Compilation message
oneway.cpp: In function 'bool isAnc(int, int)':
oneway.cpp:30:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
return !potAnc || in[potAnc] <= in[potChild] && out[potAnc] >= out[potChild];
~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:79:10: warning: unused variable 'u' [-Wunused-variable]
for(int u, v, i = 1; i <= m; ++i){
^
oneway.cpp:79:13: warning: unused variable 'v' [-Wunused-variable]
for(int u, v, i = 1; i <= m; ++i){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
