#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
int n, m, p;
const int MAX_M = 1e5;
const int MAX_N = 1e5;
char status[MAX_M];
struct Node{
vector<int> adj;
vector<int> id;
vector<int> dir;
bool vis =false;
int depth = 0;
int open = 0;
} g[MAX_N], g2[MAX_N];
int dsu[MAX_N];
int sz[MAX_N];
int get(int id){
while(dsu[id]!=id){
id = dsu[id];
}
return id;
}
void merge(int a, int b){
//cout<<a<<" and "<<b<<endl;
a = get(a);
b= get(b);
if(sz[a]<sz[b]){
dsu[a] = b;
sz[b] += sz[a];
}
else{
dsu[b] = a;
sz[a] += sz[b];
}
}
int dfs(int u, int depth, int anc){
////cout<<"dfs "<<u<<" "<<depth<<endl;
g[u].vis = true;
g[u].depth = depth;
int r = depth;
for(int i= 0; i<g[u].adj.size(); i++){
int v = g[u].adj[i];
if(g[u].id[i] != anc){
if(!g[v].vis){
int val =dfs(v, depth+1, g[u].id[i]);
if(val<=depth){
merge(u, v);
}
r = min(r, val);
}
else{
int val = g[v].depth;
if(val<=depth){
merge(u, v);
}
r = min(r, val);
}
}
}
return r;
}
pii edges[MAX_M];
const int MAX_P = 1e5;
pii pairs[MAX_P];
int dfs2(int id, int anc){
g2[id].vis = true;
int s = g2[id].open;
for(int i = 0; i<g2[id].adj.size(); i++){
if(g2[id].id[i] != anc){
int c_s = dfs2(g2[id].adj[i], g2[id].id[i]);
//cout<<g2[id].id[i]<<" "<<g2[id].dir[i]<<" "<<c_s<<endl;
if(c_s ==0){
status[g2[id].id[i]] = 'B';
}
else if(c_s >0){
if(g2[id].dir[i] == -1){
status[g2[id].id[i]] = 'R';
}
else{
status[g2[id].id[i]] = 'L';
}
}
else{
if(g2[id].dir[i] == -1){
status[g2[id].id[i]] = 'L';
}
else{
status[g2[id].id[i]] = 'R';
}
}
s+=c_s;
}
}
return s;
}
signed main(){
cin>>n>>m;
for(int i = 0; i<n; i++){
dsu[i] = i;
sz[i]=1;
}
for(int i = 0; i<m; i++){
int a, b;
cin>>a>>b;
a--;b--;
g[a].adj.push_back(b);
g[b].adj.push_back(a);
g[a].id.push_back(i);
g[b].id.push_back(i);
g[a].dir.push_back(1);
g[b].dir.push_back(-1);
edges[i].first = a;
edges[i].second = b;
}
for(int i = 0; i<n; i++){
if(!g[i].vis){
dfs(i, 0, -1);
}
}
//cout<<"dfs done"<<endl;
for(int i = 0; i<n; i++){
//cout<<dsu[i]<<endl;
}
for(int i = 0; i<m; i++){
if(get(edges[i].first) ==get(edges[i].second)){
status[i] = 'B';
//cout<<i<<" ok"<<endl;
}
else{
int a = get(edges[i].first);
int b= get(edges[i].second);
g2[a].adj.push_back(b);
g2[b].adj.push_back(a);
g2[a].id.push_back(i);
g2[b].id.push_back(i);
g2[a].dir.push_back(1);
g2[b].dir.push_back(-1);
}
}
for(int i = 0; i<m; i++){
int a= get(edges[i].first);
int b = get(edges[i].second);
}
cin>>p;
for(int i = 0; i<p; i++){
cin>>pairs[i].first>>pairs[i].second;
pairs[i].first--;pairs[i].second--;
g2[pairs[i].first].open ++;
g2[pairs[i].second].open--;
}
for(int i = 0; i<n; i++){
if(!g2[get(i)].vis){
dfs2(get(i), -1);
}
}
for(int i = 0; i<m; i++){
cout<<status[i];
}
cout<<endl;
}
Compilation message
oneway.cpp: In function 'long long int dfs(long long int, long long int, long long int)':
oneway.cpp:56:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i= 0; i<g[u].adj.size(); i++){
| ~^~~~~~~~~~~~~~~~
oneway.cpp: In function 'long long int dfs2(long long int, long long int)':
oneway.cpp:88:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 0; i<g2[id].adj.size(); i++){
| ~^~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:173:13: warning: unused variable 'a' [-Wunused-variable]
173 | int a= get(edges[i].first);
| ^
oneway.cpp:174:13: warning: unused variable 'b' [-Wunused-variable]
174 | int b = get(edges[i].second);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
23644 KB |
Output is correct |
| 2 |
Correct |
5 ms |
23644 KB |
Output is correct |
| 3 |
Correct |
5 ms |
23644 KB |
Output is correct |
| 4 |
Correct |
6 ms |
23900 KB |
Output is correct |
| 5 |
Correct |
7 ms |
23900 KB |
Output is correct |
| 6 |
Correct |
6 ms |
23644 KB |
Output is correct |
| 7 |
Correct |
6 ms |
23768 KB |
Output is correct |
| 8 |
Correct |
6 ms |
23900 KB |
Output is correct |
| 9 |
Incorrect |
5 ms |
23644 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
23644 KB |
Output is correct |
| 2 |
Correct |
5 ms |
23644 KB |
Output is correct |
| 3 |
Correct |
5 ms |
23644 KB |
Output is correct |
| 4 |
Correct |
6 ms |
23900 KB |
Output is correct |
| 5 |
Correct |
7 ms |
23900 KB |
Output is correct |
| 6 |
Correct |
6 ms |
23644 KB |
Output is correct |
| 7 |
Correct |
6 ms |
23768 KB |
Output is correct |
| 8 |
Correct |
6 ms |
23900 KB |
Output is correct |
| 9 |
Incorrect |
5 ms |
23644 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
23644 KB |
Output is correct |
| 2 |
Correct |
5 ms |
23644 KB |
Output is correct |
| 3 |
Correct |
5 ms |
23644 KB |
Output is correct |
| 4 |
Correct |
6 ms |
23900 KB |
Output is correct |
| 5 |
Correct |
7 ms |
23900 KB |
Output is correct |
| 6 |
Correct |
6 ms |
23644 KB |
Output is correct |
| 7 |
Correct |
6 ms |
23768 KB |
Output is correct |
| 8 |
Correct |
6 ms |
23900 KB |
Output is correct |
| 9 |
Incorrect |
5 ms |
23644 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
