#include <cstdio>
#include <queue>
#include <string>
#include <numeric>
using namespace std;
struct edge{
int f, t, i;
};
string ans;
//graph 1
vector<vector<edge>> adjLis1;
vector<int> dt, low;
int t;
vector<int> p;
int par(int x){
if(p[x]==x)
return x;
return p[x]=par(p[x]);
}
//graph 2
vector<edge> edgeLis;
vector<vector<edge>> adjLis2;
//graph 1: graph 2
void dfs1(int x=0, int pi=-1){
dt[x]=low[x]=t;t+=2;
for(auto i: adjLis1[x]){
int y=i.f+i.t-x;
if(dt[y]==0){
dfs1(y, i.i);
low[x]=min(low[x], low[y]);
if(dt[x]<low[y]){
//bridge
edgeLis.push_back(i);
}else{
//not bridge
p[par(x)]=par(y);
// printf("merge %d %d\n", x, y);
}
}else if(i.i!=pi){
low[x]=min(low[x], dt[y]-1);
}
}
}
//graph 1
void dfs2(int x=0){
dt[x]++;
for(auto i: adjLis1[x]){
int y=i.f+i.t-x;
if(par(x)==par(y))
ans[i.i]='B';
if(dt[y]==0)
dfs2(y);
}
}
//graph 2
vector<int> parent, depth, jump;
vector<int> direction;//012 + 048 --> parent/jump nothing, up, down
//yes, I know, p, par, pi, and parent all mean parent
void dfs3(int x){
for(auto& i: adjLis2[x]){
int y=i.f+i.t-x;
if(y==parent[x])
continue;
parent[y]=x;
depth[y]=depth[x]+1;
int j=jump[x];
jump[y]=depth[jump[j]]+depth[x]==depth[j]<<1?jump[j]:x;
dfs3(y);
}
}
void direct(int x, int y){
if(depth[x]<depth[y]){
while(depth[x]<depth[y]){
if(depth[x]<=jump[depth[y]]){
direction[y]|=8;
y=jump[y];
}else{
direction[y]|=2;
y=parent[y];
}
}
}else{
while(depth[x]>depth[y]){
if(depth[x]>=jump[depth[y]]){
direction[x]|=4;
x=jump[x];
}else{
direction[x]|=1;
x=parent[x];
}
}
}
if(x==y){
// printf("LCA: %d\n", x);
return;
}
while(parent[x]!=parent[y]){
if(jump[x]!=jump[y]){
direction[x]|=4;
x=jump[x];
direction[y]|=8;
y=jump[y];
}else{
direction[x]|=1;
x=parent[x];
direction[y]|=2;
y=parent[y];
}
}
direction[x]|=1;
direction[y]|=2;
// printf("LCA: %d\n", parent[x]);
}
void dfs4(int x){
for(auto& i: adjLis2[x]){
int y=i.f+i.t-x;
if(y==parent[x])
continue;
dfs4(y);
if(jump[y]!=x){
direction[x]|=direction[y]&12;
direction[jump[x]]|=direction[y]&12;
}
if(direction[y]&5){
if(i.f==y){
ans[i.i]='R';
}else{
ans[i.i]='L';
}
}
if(direction[y]&10){
if(i.f==y){
ans[i.i]='L';
}else{
ans[i.i]='R';
}
}
}
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
ans=string(m, 'U');
adjLis1.resize(n);
for(int i=0; i<m; i++){
edge inp;
scanf("%d%d", &inp.f, &inp.t), inp.f--, inp.t--;
inp.i=i;
adjLis1[inp.f].push_back(inp);
adjLis1[inp.t].push_back(inp);
}
dt.assign(n, 0);
low.resize(n);
t=1;
p.resize(n);
iota(p.begin(), p.end(), 0);
dfs1();
dt.assign(n, 0);
dfs2();
for(int& i: p)
i=par(i);
adjLis2.resize(n);
for(auto i: edgeLis){
i.f=p[i.f], i.t=p[i.t];
// printf("edge %d-%d\n", i.f, i.t);
adjLis2[i.f].push_back(i);
adjLis2[i.t].push_back(i);
}
int root=p[0];
parent.resize(n);
jump.resize(n);
parent[root]=jump[root]=root;
depth.resize(n);
depth[root]=0;
dfs3(root);
direction.assign(n, 0);
int q;
scanf("%d", &q);
while(q--){
int x, y;
scanf("%d%d", &x, &y), x--, y--;
x=p[x], y=p[y];
direct(x, y);
}
dfs4(root);
printf("%s\n", ans.c_str());
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
143 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
148 | scanf("%d%d", &inp.f, &inp.t), inp.f--, inp.t--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:179:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
179 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
oneway.cpp:182:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
182 | scanf("%d%d", &x, &y), x--, y--;
| ~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
