#include <bits/stdc++.h>
using namespace std;
vector<multiset<pair<int,int>>> adjlist; //node, ind or -ind if bridge
vector<int> depth;
vector<int> low; //closest to root
vector<pair<int,pair<int,int>>> bridgeedges; //ind, {n1,n2}
set<pair<int,int>> bridges;
vector<int> ind2com;
vector<vector<pair<int,int>>> comadjlist;
int n;
void tarjan(int node, int parent, int d, int ni){
//cout<<node<<" "<<parent<<" "<<d<<'\n';
depth[node]=d;
low[node]=d;
int lowest = n;
bool ispar = false;
if (ni%2==0){
ni++;
} else {
ni--;
}
for (auto p : adjlist[node]){
int newnode = p.first;
int newind = p.second;
if (ni==newind){continue;}
if (low[newnode]==n){
//not visited before
tarjan(newnode,node,d+1,newind);
if (low[newnode]>d){
//cout<<"bridge "<<node<<" "<<newnode<<'\n';
//is bridge
//cout<<"erase"<<'\n';
if (newind%2==0){
bridgeedges.push_back({newind,{node,newnode}});
bridgeedges.push_back({newind+1,{newnode,node}});
} else {
bridgeedges.push_back({newind,{node,newnode}});
bridgeedges.push_back({newind-1,{newnode,node}});
}
//cout<<"done"<<'\n';
bridges.insert({min(newnode,node),max(newnode,node)});
}
}
low[node]=min(low[node],low[newnode]);
}
}
void dfs(int ind, int numcom){
ind2com[ind]=numcom;
for (auto p : adjlist[ind]){
//if (p.second<0){continue;}
if (bridges.count({min(ind,p.first),max(ind,p.first)})){continue;}
if (ind2com[p.first]==-1){dfs(p.first,numcom);}
}
}
int kthparent[100000][20];
vector<int> upcnt;
vector<int> downcnt;
vector<char> ans;
int nc;
void treedfs(int node, int parent){
//cout<<node<<" "<<parent<<'\n';
for (auto p : comadjlist[node]){
if (p.first==parent){continue;}
depth[p.first]=depth[node]+1;
kthparent[p.first][0]=node;
treedfs(p.first,node);
}
}
void decom2k(){
for (int i = 1; i<20; i++){
for (int x = 0; x<nc; x++){
if (kthparent[x][i-1]==-1){
kthparent[x][i]=-1;
} else {
kthparent[x][i]=kthparent[kthparent[x][i-1]][i-1];
}
}
}
}
int lca(int a, int b){
if (depth[a]<depth[b]){
swap(a,b);
}
for (int i = 19; i>=0; i--){
if (kthparent[a][i]==-1){continue;}
if (depth[kthparent[a][i]]>=depth[b]){
a=kthparent[a][i];
}
}
//cout<<a<<" "<<b<<'\n';
if (a==b){return a;}
for (int i = 19; i>=0; i--){
if (kthparent[a][i]==-1){continue;}
if (kthparent[a][i]!=kthparent[b][i]){
a=kthparent[a][i];
b=kthparent[b][i];
}
}
return kthparent[a][0];
}
void ansdfs(int node, int parent){
int totup = 0;
int totdown = 0;
for (auto p : comadjlist[node]){
int ind = p.first;
if (ind==parent){continue;}
ansdfs(ind,node);
if (upcnt[ind]>0){
//p.second even if node->p.first is R
//otherwise L
//flip val
ans[p.second/2]=((p.second%2==0)?'L':'R');
} else if (downcnt[ind]>0){
//don't flip val
ans[p.second/2]=((p.second%2==0)?'R':'L');
}
totup+=upcnt[ind];
totdown+=downcnt[ind];
}
upcnt[node]+=totup;
downcnt[node]+=totdown;
//cout<<node<<" "<<upcnt[node]<<" "<<downcnt[node]<<'\n';
assert(!(upcnt[node]>0&&downcnt[node]>0));
}
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
int m;
cin>>n>>m;
adjlist.resize(n);
depth.resize(n,0);
low.resize(n,n);
for (int i = 0; i<m; i++){
int a,b;
cin>>a>>b;
a--;b--;
if (a==b){continue;}
adjlist[a].insert({b,i*2});
adjlist[b].insert({a,i*2+1});
}
ans.resize(m,'B');
tarjan(0,-1,0,-1);
ind2com.resize(n,-1);
int numcom = 0;
for (int i = 0; i<n; i++){
if (ind2com[i]!=-1){continue;}
dfs(i,numcom);
numcom++;
}
//cout<<numcom<<" "<<bridgeedges.size()<<'\n';
comadjlist.resize(numcom);
for (auto p : bridgeedges){
comadjlist[ind2com[p.second.first]].push_back({ind2com[p.second.second],p.first});
}
/*for (int i = 0; i<numcom; i++){
cout<<i<<": ";
for (auto j : comadjlist[i]){
cout<<j.first<<", ";
}cout<<'\n';
}*/
assert(numcom==bridgeedges.size()/2+1);
nc=numcom;
depth.resize(nc,0);
kthparent[0][0]=-1;
treedfs(0,-1);
decom2k();
int p;
cin>>p;
upcnt.resize(nc);
downcnt.resize(nc);
for (int i = 0; i<p; i++){
int a,b;
cin>>a>>b;
a--;b--;
a=ind2com[a];
b=ind2com[b];
if (a==b){continue;}
int l = lca(a,b);
//cout<<a<<" "<<b<<" "<<l<<'\n';
upcnt[a]++;
upcnt[l]--;
downcnt[l]--;
downcnt[b]++;
}
ansdfs(0,-1);
for (char c : ans){
cout<<c;
}cout<<'\n';
}
Compilation message
oneway.cpp: In function 'void tarjan(int, int, int, int)':
oneway.cpp:18:6: warning: unused variable 'lowest' [-Wunused-variable]
int lowest = n;
^~~~~~
oneway.cpp:19:7: warning: unused variable 'ispar' [-Wunused-variable]
bool ispar = false;
^~~~~
In file included from /usr/include/c++/7/cassert:44:0,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
from oneway.cpp:1:
oneway.cpp: In function 'int main()':
oneway.cpp:171:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(numcom==bridgeedges.size()/2+1);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
