#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
//mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN = 2e5+5;
const int mod = 998244353;
const int mxlogN = 20;
const int mxK = 26;
const ll inf = 1e9;
struct edge
{
int u, v, root; bool cut; int way;
int other(int i)
{
return i^u^v;
}
};
edge es[mxN];
int vis[mxN],lowlink[mxN],_time[mxN],_timer;
vector<int> adj[mxN];
void dfs(int i, int p=-1) ///parent edge
{
lowlink[i]=_time[i]=_timer++;
vis[i]=1;
for(int e:adj[i])
{
int j=es[e].other(i);
if(j==p||vis[j]==2) continue;
if(vis[j]) lowlink[i]=min(lowlink[i],_time[j]);
else
{
dfs(j,i);
lowlink[i]=min(lowlink[i],lowlink[j]);
if(lowlink[j]>_time[i]) es[e].cut=1;
}
}
vis[i]=2;
}
int sz=0;
int root[mxN];
void dfs2(int i, int r)
{
vis[i]=1;
root[i]=r;
for(int e:adj[i])
{
int j=es[e].other(i);
if(es[e].cut||vis[j]) continue;
dfs2(j,r);
}
}
vector<int> adjc[mxN];
int up[mxlogN][mxN], down[mxN], where[mxN], pe[mxN];
void dfs3(int i, int p=-1, int d=0)
{
if(~p) up[0][i]=es[p].other(i);
else up[0][i]=i;
pe[i]=p;
vis[i]=1;
down[i]=d;
where[i]=i;
for(int j=1; j<mxlogN; j++) up[j][i]=up[j-1][up[j-1][i]];
for(int e:adjc[i]) if(e!=p) dfs3(es[e].other(i),e,d+1);
}
int goup(int i, int k)
{
if(!k) return i;
for(int j=mxlogN-1; j>=0; j--)
{
if(k>(1<<j))
{
k-=1<<j;
i=up[j][i];
}
}
return up[0][i];
}
int find_lca(int i, int j)
{
if(down[i]<down[j]) swap(i,j);
i = goup(i,down[i]-down[j]);
if(i==j) return i;
for(int k=mxlogN-1; k>=0; k--)
{
if(up[k][i]!=up[k][j])
{
i=up[k][i], j=up[k][j];
}
}
return up[0][i];
}
void setup(int n, int m)
{
for(int i=0; i<n; i++) if(!vis[i]) dfs(i);
for(int i=0; i<n; i++) vis[i]=0;
for(int i=0; i<n; i++) if(!vis[i]) dfs2(i,sz++);
for(int i=0; i<m; i++)
{
if(es[i].cut)
{
int u=root[es[i].u], v=root[es[i].v];
es[i].u=u, es[i].v=v;
adjc[u].push_back(i);
adjc[v].push_back(i);
}
}
for(int i=0; i<sz; i++) vis[i]=0;
for(int i=0; i<sz; i++) if(!vis[i]) dfs3(i);
}
void clear_all()
{
///clear
}
int get(int i)
{
if(!~pe[where[i]]) return where[i];
if(~es[pe[where[i]]].way) where[i]=get(up[0][where[i]]);
return where[i];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
for(int i=0; i<m; i++)
{
int u,v; cin >> u >> v; u--, v--;
es[i]={u,v};
es[i].cut=0;
es[i].root=-1;
es[i].way=-1;
adj[u].push_back(i);
adj[v].push_back(i);
}
setup(n,m);
int p; cin >> p;
while(p--)
{
int x, y; cin >> x >> y; x--, y--;
x=root[x], y=root[y];
int lca=find_lca(x,y);
while(1)
{
x=get(x);
if(down[x]<=down[lca]) break;
if(es[pe[x]].u==x) es[pe[x]].way=0;
else es[pe[x]].way=1;
}
while(1)
{
y=get(y);
if(down[y]<=down[lca]) break;
if(es[pe[y]].v==y) es[pe[y]].way=0;
else es[pe[y]].way=1;
}
}
for(int i=0; i<m; i++)
{
if(!~es[i].way) cout << "B";
else if(es[i].way) cout << "L";
else cout << "R";
}
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9812 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9860 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9812 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9860 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9812 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9860 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
