#include<bits/stdc++.h>
#define I inline void
using namespace std ;
using ll = long long ;
using ld = long double ;
const int N = 1e5 + 7 ;
int n , m;
string ans ;
std::vector<pair<int , int > > adj[N];
int tim[N] ;
int t , tmr ;
int fat[N] , par[N] , fate[N] ;
int st[N] , en[N] , a[N] ;
int up[N][18] ;
int fin(int x){
return fat[x] = (x == fat[x] ? x : fin(fat[x])) ;
}
I link(int u , int v){
int uu = fin(u) ;
int vv = fin(v) ;
if(uu != vv){
fat[uu] = vv ;
}
}
I rec(int u , int v , int mask){
if(tim[u] < tim[v])swap(u , v) ;
while(u != v){
if(!a[fate[u]])
a[fate[u]] = mask ;
u = par[u] ;
}
}
bool upper(int u , int v){
return st[v] >= st[u] && en[v] <=en[u] ;
}
int lca(int u , int v){
if(upper(u , v))return u ;
if(upper(v , u))return v ;
for(int i = 17 ; i>= 0 ;i--)
if(!upper(up[u][i] , v))
u = up[u][i];
return up[u][0] ;
}
I dfs(int x , int p ){
tim[x] = ++ t;
st[x] = ++ tmr ;
for(auto u : adj[x]){
if(u.first == p)continue ;
if(tim[u.first]){
rec(x , u.first , 3) ;
a[u.second] = 3 ;
}else{
par[u.first] = x ;
fate[u.first] = u.second ;
dfs(u.first , x) ;
}
}
en[x] = ++ tmr ;
}
I pre(){
for(int i = 0 ; i < N ;i++)
fat[i] = i ;
}
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
//freopen("in.in" , "r" , stdin) ;
pre() ;
cin >> n >> m ;
for(int i = 0 ;i < m ;i++){
int u , v;
cin >> u >> v ;
adj[u].push_back({v , i}) ;
adj[v].push_back({u , i }) ;
}
dfs(1, 1 ) ;
int k ; cin >> k ;
for(int i = 0 ;i < k ;i++){
int u , v ;
cin >> u >> v;
int lc = lca(u , v) ;
rec(u , lc , 1) ;
rec(v , lc , 2) ;
}
for(int i = 0 ;i < m;i++){
if(a[i] == 3)ans+='B' ;
else if(a[i] == 1)ans+='R' ;
else if(a[i] == 2) ans+='L' ;
else ans+='B' ;
}
cout<< ans ;
return 0 ;
}
Compilation message
oneway.cpp: In function 'int lca(int, int)':
oneway.cpp:50:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(int i = 17 ; i>= 0 ;i--)
^~~
oneway.cpp:53:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
return up[u][0] ;
^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3011 ms |
3072 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3011 ms |
3072 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3011 ms |
3072 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
