#include<bits/stdc++.h>
#define lcm(a,b) (a/__gcd(a,b))*b
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define F first
#define S second
#define mp make_pair
//salida rapida "\n"
//DECIMALES fixed<<sp(n)<<x<<endl;
//gcd(a,b)= ax + by
//gcd(a,b)=gcd(a-b,b) a>=b
//lCB x&-x
//set.erase(it) - ersases the element present at the required index//auto it = s.find(element)
//set.find(element) - iterator pointing to the given element if it is present else return pointer pointing to set.end()
//set.lower_bound(element) - iterator pointing to element greater than or equal to the given element
//set.upper_bound(element) - iterator pointing to element greater than the given element
// | ^
//__builtin_popcount(x)
using namespace std;
const int MA=1e5+5;
vector<pair<int,int> > G[MA];
int vis[MA];
int arc[MA];
int num=0;
set<pair<int,int> >st;
int puente[MA];
string res;
void tarjan(int nodo, int ant){
num++;
vis[nodo]=arc[nodo]=num;
for(int it =0;it<G[nodo].size();it++){
int to=G[nodo][it].F,ind=G[nodo][it].S;
if(ind==ant)continue;
if(vis[to]==0){
tarjan(to,ind);
if(arc[to]>vis[nodo]){
puente[ind]=1;
}
arc[nodo]=min(arc[nodo],arc[to]);
}else{
arc[nodo]=min(arc[nodo],vis[to]);
}
}
}
vector<pair<int,int> > G2[MA];
int C[MA];
int color=0;
void coloring(int nodo){
cout<<nodo<<endl;
C[nodo]=color;
for(int i=0;i<G[nodo].size();i++){
int to=G[nodo][i].F,ind=G[nodo][i].S;
if(puente[ind] or C[to])continue;
coloring(to);
}
}
int B[MA];
void dfs(int nodo, int padre){
for(int i=0;i<G2[nodo].size();i++){
int to=G2[nodo][i].F,ind=G2[nodo][i].S;
if(to==padre)continue;
B[to]=ind;
dfs(to,nodo);
}
}
int main()
{
int n,m,p,a,b;
cin>>n>>m;
vector<pair<int,int> >E;
for(int i=0;i<m;i++){
cin>>a>>b;
G[a].pb({b,i});G[b].pb({a,i});
E.pb({a,b});
}
res.assign(m,'B');
for(int i=1;i<=n;i++){
if(vis[i]==0){
tarjan(i,-1);
}
}
for(int i=1;i<=n;i++){
if(C[i])continue;
color++;
coloring(i);
}
for(int i=0;i<m;i++){
if(puente[i]==0)continue;
int A=C[E[i].F],B=C[E[i].S];
if(A==B)continue;
//cout<<"UNO "<<A<<" "<<B<<endl;
G2[A].pb({B,i});
G2[B].pb({A,i});
}
cin>>p;
for(int i=0;i<p;i++){
cin>>a>>b;
a=C[a],b=C[b];
if(a==b)continue;
dfs(a,-1);
int nodo=b;
while(nodo!=a){
int ind=B[nodo];
int from=C[E[ind].F];
if(from==nodo){
from=C[E[ind].S];
res[ind]='L';
}else{
res[ind]='R';
}
nodo=from;
}
}
cout<<res<<endl;
return 0;
}
Compilation message
oneway.cpp: In function 'void tarjan(int, int)':
oneway.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int it =0;it<G[nodo].size();it++){
| ~~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void coloring(int)':
oneway.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=0;i<G[nodo].size();i++){
| ~^~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<G2[nodo].size();i++){
| ~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
