#include<bits/stdc++.h>
using namespace std;
struct wi{
vector<int> Q,Q2;
int skoki[20];
int pocz=0,kon=0;
int most=0;
int low=0;
bool odw=0;
int pree=0;
int poz=0;
int nr_do_ojca;
}*w;
int t[200000][2];
int wypisz[200000];
bool essa[200000];
int pre=1;
void dodaj(int x)
{
int gdzie=0;
while(w[w[x].skoki[gdzie]].skoki[gdzie]!=0)
{
w[x].skoki[gdzie+1]=w[w[x].skoki[gdzie]].skoki[gdzie];
gdzie++;
}
}
void reku(int x,int ojc)
{
w[x].poz=w[ojc].poz+1;
w[x].skoki[0]=ojc;
dodaj(x);
w[x].odw=1;
w[x].pree=pre;
w[x].low=pre;
pre++;
for(int i=0;i<w[x].Q.size();i+=2)
{
int pom=w[x].Q[i];
if(pom==ojc)
continue;
if(w[pom].odw)
w[x].low=min(w[x].low,w[pom].pree);
else{
w[pom].Q2.push_back(x);
w[x].Q2.push_back(pom);
w[pom].Q2.push_back(w[x].Q[i+1]);
w[x].Q2.push_back(w[x].Q[i+1]);
w[pom].nr_do_ojca=w[x].Q[i+1];
reku(pom,x);
w[x].low=min(w[x].low,w[pom].low);
if(w[pom].low>w[x].pree)
w[pom].most=1;
}
}
}
int lcaa(int x,int y)
{
if(w[x].poz>w[y].poz)
swap(x,y);
for(int i=19;i>=0;i--)
if(w[w[y].skoki[i]].poz>=w[x].poz)
y=w[y].skoki[i];
if(x==y)
return x;
for(int i=19;i>=0;i--)
if(w[x].skoki[i]!=w[y].skoki[i])
{
x=w[x].skoki[i];
y=w[y].skoki[i];
}
return w[x].skoki[0];
}
void reku2(int x,int ojc)
{
for(int i=0;i<w[x].Q2.size();i+=2)
{
int pom=w[x].Q2[i];
if(pom==ojc)
continue;
reku2(pom,x);
w[x].pocz+=w[pom].pocz;
w[x].kon+=w[x].kon;
}
if(w[x].pocz==0 && w[x].kon==0)
return;
if(w[x].most==0)
return;
if(w[x].pocz!=0 && w[x].kon!=0)
{
int mam=w[x].nr_do_ojca;
essa[mam]=1;
return;
}
if(w[x].pocz==0 && w[x].kon!=0)
{
int mam=w[x].nr_do_ojca;
if(t[mam][0]==x)
{
if(wypisz[mam]==2)
essa[mam]=1;
else wypisz[mam]=1;
}
else {
if(wypisz[mam]==1)
essa[mam]=1;
else wypisz[mam]=2;
}
}
else{
int mam=w[x].nr_do_ojca;
if(t[mam][0]==x)
{
if(wypisz[mam]==1)
essa[mam]=1;
else wypisz[mam]=2;
}
else {
if(wypisz[mam]==2)
essa[mam]=1;
else wypisz[mam]=1;
}
}
}
int32_t main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int n,m,x,y;
cin>>n>>m;
w=new wi[n+3];
for(int i=1;i<=m;i++)
{
cin>>x>>y;
w[x].Q.push_back(y);
w[y].Q.push_back(x);
w[x].Q.push_back(i);
w[y].Q.push_back(i);
t[i][0]=x;
t[i][1]=y;
}
reku(1,0);
int zap;
cin>>zap;
while(zap--)
{
cin>>x>>y;
w[x].pocz++;
w[y].kon++;
//cout<<x<<" "<<y<<": "<<lcaa(x,y)<<"\n";
int lca=lcaa(x,y);
w[lca].pocz--;
w[lca].kon--;
}
reku2(1,0);
for(int i=1;i<=m;i++)
{
if(wypisz[i]==0 || essa[i]==1)
cout<<"B";
else if(wypisz[i]==1)
cout<<"L";
else if(wypisz[i]==2)
cout<<"R";
}
return 0;
}
Compilation message
oneway.cpp: In function 'void reku(int, int)':
oneway.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0;i<w[x].Q.size();i+=2)
| ~^~~~~~~~~~~~~~
oneway.cpp: In function 'void reku2(int, int)':
oneway.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i=0;i<w[x].Q2.size();i+=2)
| ~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
