#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
int n, m;
pair<pair<int, int>, char> edgeList[100000];
vector<pair<pair<int, int>, int> > adjList[100001];
int visOrd[100001];
int visLow[100001];
int parent[100001];
int counter;
void dfs(int node){
visOrd[node]=visLow[node]=counter;
counter++;
bool countParent=false;
for(int i=0;i<adjList[node].size();i++){
if(visOrd[adjList[node][i].first.first]==-1){
parent[adjList[node][i].first.first]=node;
dfs(adjList[node][i].first.first);
}
if(adjList[node][i].first.first!=parent[node]||countParent){
visLow[node]=min(visLow[node], visLow[adjList[node][i].first.first]);
adjList[node][i].first.second=visLow[adjList[node][i].first.first]>visOrd[node]?1:0;
}
if(adjList[node][i].first.first==parent[node]){
countParent=true;
}
}
}
int parent2[100001], depth[100001];
int root(int a){
int b=a;
while(b!=parent2[b]){
b=parent2[b];
}
return parent2[a]=b;
}
bool isCon(int a, int b){
return root(a)==root(b);
}
void join(int a, int b){
if(depth[root(a)]<root(b)){
parent2[root(a)]=root(b);
}
else if(depth[root(b)]<root(a)){
parent2[root(b)]=root(a);
}
else{
parent2[root(b)]=root(a);
depth[root(a)]++;
}
}
vector<pair<int, int> > adjList2[100001];
int firstVis2[100001];
int visOrd2[199999];
int depth2[100001];
int LCATable[18][199999];
int counter2;
void dfs2(int node){
firstVis2[node]=counter2;
visOrd2[counter2]=node;
counter2++;
for(int i=0;i<adjList2[node].size();i++){
if(firstVis2[adjList2[node][i].first]==-1){
depth2[adjList2[node][i].first]=depth2[node]+1;
dfs2(adjList2[node][i].first);
visOrd2[counter2]=node;
counter2++;
}
}
}
void initLCA(){
for(int i=0;i<2*n-1;i++){
LCATable[0][i]=i;
}
for(int i=1;(1<<i)<=2*n-1;i++){
for(int j=0;j+(1<<i)<=2*n-1;j++){
if(depth2[visOrd2[LCATable[i-1][j]]]>depth2[visOrd2[LCATable[i-1][j+(1<<(i-1))]]]){
LCATable[i][j]=LCATable[i-1][j+(1<<(i-1))];
}
else{
LCATable[i][j]=LCATable[i-1][j];
}
}
}
}
int LCA(int a, int b){
int l=min(firstVis2[a], firstVis2[b]), r=max(firstVis2[a], firstVis2[b]);
int mini=r, diff=r-l;
for(int i=0;i<18;i++){
if(diff&(1<<i)){
if(depth2[visOrd2[LCATable[i][l]]]<depth2[visOrd2[mini]]){
mini=LCATable[i][l];
}
l+=(1<<i);
}
}
return visOrd2[mini];
}
bool vis3[100001];
pair<int, int> dir[100001];
void dfs3(int node){
vis3[node]=true;
for(int i=0;i<adjList2[node].size();i++){
if(!vis3[adjList2[node][i].first]){
dfs3(adjList2[node][i].first);
if(depth2[dir[adjList2[node][i].first].first]<depth2[dir[node].first]){
dir[node]=dir[adjList2[node][i].first];
}
if(depth2[dir[adjList2[node][i].first].first]<depth2[adjList2[node][i].first]){
if((depth2[root(edgeList[adjList2[node][i].second].first.first)]<depth2[root(edgeList[adjList2[node][i].second].first.second)])==(dir[adjList2[node][i].first].second==-1)){
edgeList[adjList2[node][i].second].second='L';
}
else{
edgeList[adjList2[node][i].second].second='R';
}
}
}
}
}
int main(){
scanf("%d%d", &n, &m);
for(int i=0;i<m;i++){
scanf("%d%d", &edgeList[i].first.first, &edgeList[i].first.second);
edgeList[i].second='B';
adjList[edgeList[i].first.first].push_back(make_pair(make_pair(edgeList[i].first.second, -1), i));
adjList[edgeList[i].first.second].push_back(make_pair(make_pair(edgeList[i].first.first, -1), i));
}
for(int i=1;i<n+1;i++){
visOrd[i]=-1;
}
counter=0;
parent[1]=0;
dfs(1);
for(int i=1;i<n+1;i++){
parent2[i]=i;
depth[i]=1;
}
for(int i=1;i<n+1;i++){
for(int j=0;j<adjList[i].size();j++){
if(adjList[i][j].first.second==0){
if(!isCon(i, adjList[i][j].first.first)){
join(i, adjList[i][j].first.first);
}
}
}
}
for(int i=1;i<n+1;i++){
for(int j=0;j<adjList[i].size();j++){
if(adjList[i][j].first.second==1){
adjList2[root(i)].push_back(make_pair(root(adjList[i][j].first.first), adjList[i][j].second));
adjList2[root(adjList[i][j].first.first)].push_back(make_pair(root(i), adjList[i][j].second));
}
}
}
for(int i=1;i<n+1;i++){
firstVis2[i]=-1;
}
counter2=0;
depth2[root(1)]=1;
dfs2(root(1));
initLCA();
int p;
scanf("%d", &p);
for(int i=1;i<n+1;i++){
dir[i]=make_pair(i, 0);
}
while(p--){
int x, y;
scanf("%d%d", &x, &y);
int temp=LCA(root(x), root(y));
if(depth2[temp]<depth2[dir[root(x)].first]){
dir[root(x)]=make_pair(temp, -1);
}
if(depth2[temp]<depth2[dir[root(y)].first]){
dir[root(y)]=make_pair(temp, 1);
}
}
for(int i=1;i<n+1;i++){
vis3[i]=false;
}
dfs3(root(1));
for(int i=0;i<m;i++){
printf("%c", edgeList[i].second);
}
return 0;
}
Compilation message
oneway.cpp: In function 'void dfs(int)':
oneway.cpp:21:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adjList[node].size();i++){
~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int)':
oneway.cpp:74:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adjList2[node].size();i++){
~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs3(int)':
oneway.cpp:119:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adjList2[node].size();i++){
~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:156:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<adjList[i].size();j++){
~^~~~~~~~~~~~~~~~~~
oneway.cpp:165:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<adjList[i].size();j++){
~^~~~~~~~~~~~~~~~~~
oneway.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &edgeList[i].first.first, &edgeList[i].first.second);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:180:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p);
~~~~~^~~~~~~~~~
oneway.cpp:186: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 |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
