///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define li long int
#define ld long double
#define append push_back
#define add insert
#define nl "\n"
#define ff first
#define ss second
#define pii pair<int,int>
#define pic pair<int,char>
#define all(x) (x).begin(),(x).end()
#define sum(a) accumulate(all(a),0)
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL)
#define terminator main
#define N 100001
char c[N];
int up[N];
int cup[N];
int Par[N];
int par[N];
int cpar[N];
int dept[N];
pii edge[N];
vector<pii> a[N];
vector<pii> g[N];
int root(int v){
if(!Par[v]) return v;
Par[v]=root(Par[v]);
return Par[v];
}
void merge(int v,int u){
v=root(v);
u=root(u);
Par[u]=v;
}
bool same(int v,int u){
return (root(v)==root(u));
}
void dfs(int v){
up[v]=dept[v];
for(auto& i:a[v]){
if(!dept[i.ff] || dept[i.ff]>dept[v])
cup[v]--;
else cup[v]++;
if(!dept[i.ff]){
dept[i.ff]=dept[v]+1;
cpar[i.ff]=i.ss;
par[i.ff]=v;
dfs(i.ff);
}
else up[v]=min(up[v],dept[i.ff]);
}
cup[par[v]]+=cup[v];
if(cup[v]>1){
up[par[v]]=min(up[par[v]],up[v]);
merge(v,par[v]);
}
}
void dfs2(int v,int u){
dept[v]=dept[u]+1;
par[v]=u;
for(auto& i:g[v]){
if(i.ff==u) continue;
cpar[i.ff]=i.ss;
dfs2(i.ff,v);
}
}
void solve(){
pii pi,pj;
int n,m,o,p,q,r;
cin>>n>>m;
for(int i=0;i<m;i++){
c[i]='B';
cin>>p>>q;
edge[i]={p,q};
a[p].append({q,i});
a[q].append({p,i});
}
dept[1]=1;
dfs(1);
for(int i=2;i<=n;i++){
if(same(i,par[i])) continue;
p=root(i);
q=root(par[i]);
g[p].append({q,cpar[i]});
g[q].append({p,cpar[i]});
}
dfs2(root(1),0);
cin>>o;
while(o--){
cin>>p>>q;
p=root(p);
q=root(q);
while(p!=q){
if(dept[p]>dept[q]){
pj={p,par[p]};
pi=edge[cpar[p]];
pi.ff=root(pi.ff);
pi.ss=root(pi.ss);
if(pj==pi)
c[cpar[p]]='R';
else c[cpar[p]]='L';
p=par[p];
}
else{
pj={q,par[q]};
pi=edge[cpar[q]];
pi.ff=root(pi.ff);
pi.ss=root(pi.ss);
if(pj==pi)
c[cpar[q]]='L';
else c[cpar[q]]='R';
q=par[q];
}
}
}
for(int i=0;i<m;i++)
cout<<c[i];
}
int terminator(){
L0TA;
solve();
return 0;
}
Compilation message
oneway.cpp: In function 'void solve()':
oneway.cpp:73:19: warning: unused variable 'r' [-Wunused-variable]
73 | int n,m,o,p,q,r;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3058 ms |
6748 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3058 ms |
6748 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3058 ms |
6748 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
