#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ii=pair<int,int>;
vector<array<int,3>> bridge;
int timer=0;
int num[100005],low[100005];
vector<ii> adj[100005];
vector<ii> edge;
char ans[100005];
map<ii,bool> cb;
vector<array<int,3>> change;
void dfs(int u,int pre) {
timer++;
num[u]=timer;
low[u]=num[u];
for(ii v:adj[u]) {
//cout << v.first << endl;
if(v.first==pre) continue;
if(!num[v.first] ) {
dfs(v.first,u);
low[u]=min(low[u],low[v.first]);
if(low[v.first]==num[v.first]) {
bridge.push_back({u,v.first,v.second});
cb[{u,v.first}]=1;
cb[{v.first,u}]=1;
}
}
else {
low[u]=min(low[u],num[v.first]);
}
}
return;
}
int d[100005];
void bfs(int s,int t) {
for(int i=1;i<=100000;i++) d[i]=0;
d[s]=1;
queue<int> q;
q.push(s);
while(!q.empty()) {
int u=q.front();
q.pop();
for(ii v:adj[u]) {
if(d[v.first]==0) {
d[v.first]=d[u]+1;
q.push(v.first);
}
}
}
int k=t;
while(k!=s) {
for(ii v:adj[k]) {
if(d[v.first]==d[k]-1) {
//cout << k << ' ' << v.first << endl;
if(cb[{k,v.first}]) change.push_back({v.first,k,v.second});
k=v.first;
break;
}
}
}
return;
}
int main()
{
int n,m;
cin >> n >> m;
edge.push_back({0,0});
for(int i=1;i<=m;i++) {
int x,y;
cin >> x >> y;
adj[x].push_back({y,i});
adj[y].push_back({x,i});
edge.push_back({x,y});
ans[i]='B';
}
dfs(1,0);
int k;
cin >> k;
for(int i=0;i<k;i++) {
int x,y;
cin >> x >> y;
bfs(x,y);
}
for(array<int,3> e:change) {
int u=e[0];
int v=e[1];
if(u==edge[e[2]].first && v==edge[e[2]].second) {
ans[e[2]]='R';
}
else {
ans[e[2]]='L';
}
}
map<ii,int> mp;
for(int i=1;i<=m;i++) {
cout << ans[i];
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
