#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fori(x,a,b) for(int x=a;x<=b;x++)
#define ford(x,a,b) for(int x=a;x>=b;x--)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define getbit(x,i) ((x>>i)&1)
#define batbit(x,i) (x|(1ll<<i))
#define tatbit(x,i) (x&~(1<<i))
#define gg exit(0);
const int N = 1e5 + 10;
int n,m,x,y,scc,id[N],sl[N],dd[N],low[N],num[N],it;
stack<int> s;
vector<int> ke[N];
void dfs(int u,int pr)
{
low[u] = num[u] = ++it;
dd[u] = 1;
s.push(u);
forv(v,ke[u]) if(v!=pr)
{
if(!dd[v])
{
dfs(v,u);
low[u] = min(low[u],low[v]);
}
else if(dd[v]==1) low[u] = min(low[u],num[v]);
}
if(low[u]==num[u])
{
scc++;
int v;
do
{
v = s.top();s.pop();
dd[v] = 2;
id[v] = scc;
sl[scc]++;
}while(u!=v);
}
}
vector<ii> ad[N];
int dep[N],pd[N][25];
ii e[N],pa[N];
void dfs1(int u,int pr)
{
dd[u] = 1;
fori(i,1,log2(scc)) pd[u][i] = pd[pd[u][i-1]][i-1];
forv(v,ad[u]) if(!dd[v.fi])
{
pd[v.fi][0] = u;
pa[v.fi] = {u,v.se};
dep[v.fi] = dep[u] + 1;
dfs1(v.fi,u);
}
}
int lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
int del = dep[u]-dep[v];
ford(i,log2(scc),0) if(getbit(del,i)) u = pd[u][i];
if(u==v) return u;
ford(i,log2(scc),0) if(pd[u][i]!=pd[v][i])
u = pd[u][i],v = pd[v][i];
return pd[u][0];
}
char sol[N];
int dir[N];
void direct(int x,int anc,int ok)
{
if(x==anc) return;
if(dir[x]==0)
{
dir[x] = ok;
int i = pa[x].se,y = pa[x].fi;
int a = id[e[i].fi],b = id[e[i].se];
if(ok==-1)
{
if(a==x && b==y) sol[i] = 'R';
else sol[i] = 'L';
}
else
{
if(a==y && b==x) sol[i] = 'R';
else sol[i] = 'L';
}
direct(y,anc,ok);
}
else if(dir[x]!=ok) return;//TH ko lam dc;
}
main()
{
//freopen("task.inp","r",stdin);
fasty;
cin>>n>>m;
fori(i,1,m)
{
cin>>x>>y;
ke[x].pb(y),ke[y].pb(x);
e[i] = {x,y};
}
fori(i,1,n) if(!dd[i]) dfs(i,0);
fori(i,1,m)
{
int u = e[i].fi,v = e[i].se;
if(id[u]!=id[v]) ad[id[u]].pb({id[v],i}),ad[id[v]].pb({id[u],i});
}
reset(dd,0);
fori(i,1,scc) if(!dd[i]) dfs1(i,0);
vector<pair<int,ii> > ord;
int p;cin>>p;
fori(i,1,p)
{
cin>>x>>y;
x = id[x],y = id[y];
int tmp = dep[(x,y)];
ord.pb({tmp,{x,y}});
}
fori(i,1,m) sol[i] = 'B';
sort(all(ord));//theo solution la de tinh cho nhanh
forv(i,ord)
{
int a = i.se.fi,b = i.se.se,l = lca(a,b);
direct(a,l,-1);
direct(b,l,1);
}
fori(i,1,m) cout<<sol[i];
}
Compilation message
oneway.cpp:108:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
108 | main()
| ^~~~
oneway.cpp: In function 'int main()':
oneway.cpp:135:24: warning: left operand of comma operator has no effect [-Wunused-value]
135 | int tmp = dep[(x,y)];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
5680 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
5680 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5452 KB |
Output is correct |
| 4 |
Incorrect |
4 ms |
5680 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
