#include <bits/stdc++.h>
using namespace std;
const int MN = 1e5+5, LG = 19;
int N, M, Q, S, i, x, y, vis[MN][2], sp[MN][LG], cmp[MN], st[MN], nxt, ans[MN], u[MN], d[MN], dep[MN];
vector<pair<int,int>> adj[MN], cadj[MN];
stack<int> s;
pair<int,int> ree[MN];
string ans2;
void dfs(int n,int id){
vis[n][0]=vis[n][1]=++nxt;
st[n]=1; s.push(n);
for(auto v : adj[n]){
if(v.second==id) continue;
if(!vis[v.first][0]){
dfs(v.first, v.second);
vis[n][1]=min(vis[n][1],vis[v.first][1]);
}
else if(st[v.first]){
vis[n][1]=min(vis[n][1],vis[v.first][0]);
}
}
if(vis[n][0]==vis[n][1]){
S++;
while(s.size()&&s.top()!=n){
int x = s.top(); s.pop();
cmp[x] = S;
}
int x = s.top(); s.pop();
cmp[x] = S;
}
}
void ddfs(int n,int p,int d){
sp[n][0] = p; dep[n] = d;
for(auto v : cadj[n]){
if(v.first==p) continue;
ddfs(v.first, n, d+1);
}
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
for(int i=LG-1;i>=0;i--){
if((1<<i)<=dep[x]-dep[y])
x = sp[x][i];
}
if(x==y) return x;
for(int i=LG-1;i>=0;i--){
if(sp[x][i]!=sp[y][i]){
x = sp[x][i];
y = sp[y][i];
}
}
return sp[x][0];
}
pair<int,int> solve(int n,int p){
int a=u[n], b=d[n];
for(auto v : cadj[n]){
if(v.first==p) continue;
auto t = solve(v.first, n);
a += t.first, b += t.second;
}
if(a>0){
for(int i=0;i<cadj[n].size();i++){
if(cadj[n][i].first==p){
ans[cadj[n][i].second]=1;
break;
}
}
}
else if(b>0){
for(int i=0;i<cadj[n].size();i++){
if(cadj[n][i].first==p){
ans[cadj[n][i].second]=2;
break;
}
}
}
return make_pair(a,b);
}
int main(){
for(scanf("%d%d",&N,&M),i=1;i<=M;i++){
scanf("%d%d",&x,&y);
adj[x].push_back({y,i});
adj[y].push_back({x,i});
ree[i]={x,y};
}
for(i=1;i<=N;i++){
if(!vis[i][0]) dfs(i,0);
}
for(i=1;i<=N;i++){
for(auto v : adj[i]){
if(cmp[v.first]!=cmp[i])
cadj[cmp[i]].push_back({cmp[v.first],v.second});
}
}
ddfs(1,0,1);
for(int j=1;j<LG;j++){
for(i=1;i<=S;i++)
sp[i][j]=sp[sp[i][j-1]][j-1];
}
for(scanf("%d",&Q),i=1;i<=Q;i++){
scanf("%d%d",&x,&y);
if(cmp[x]==cmp[y]) continue;
x = cmp[x], y = cmp[y];
int a = lca(x,y);
u[x]++; u[a]--;
d[y]++; d[a]--;
}
solve(1, 0);
for(i=1;i<=M;i++){
if(ans[i]){
tie(x,y)=ree[i];
if(dep[cmp[x]]<dep[cmp[y]]){
if(ans[i]==2) ans2.push_back('R');
else ans2.push_back('L');
}
else{
if(ans[i]==2) ans2.push_back('L');
else ans2.push_back('R');
}
}
else ans2.push_back('B');
}
printf("%s\n",ans2.c_str());
return 0;
}
Compilation message
oneway.cpp: In function 'std::pair<int, int> solve(int, int)':
oneway.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cadj[n].size();i++){
~^~~~~~~~~~~~~~~
oneway.cpp:75:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cadj[n].size();i++){
~^~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:86:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(scanf("%d%d",&N,&M),i=1;i<=M;i++){
~~~~~~~~~~~~~~~~~~~^~~~
oneway.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
oneway.cpp:106:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(scanf("%d",&Q),i=1;i<=Q;i++){
~~~~~~~~~~~~~~^~~~
oneway.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
