#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 1e5 + 5;
typedef pair<int , int> ipair;
int n , m;
vector<ipair> adj[N];
int vis[N] , bridges[N] , disc[N] , low[N] , comp[N] , sum[N] , most[N];
ipair edges[N];
char ans[N];
struct Node{
int cmp , id , u , v;
};
vector<Node>newG[N];
void ini(){memset(vis , 0 , sizeof(vis));}
int dtime;
void dfs(int u , int p){
vis[u] = 1;
disc[u] = low[u] = dtime++;
for(ipair X : adj[u]){
int v = X.f , id = X.s;
if(v == p) continue;
if(!vis[v]){
dfs(v , u);
if(disc[u] < low[v]) bridges[id] = 1;
low[u] = min(low[u] , low[v]);
} else low[u] = min(low[u] , disc[v]);
}
}
void DFS(int u , int x){
vis[u] = 1;
comp[u] = x;
most[x]++;
for(ipair X : adj[u]){
int v = X.f , id = X.s;
if(!bridges[id] && !vis[v]) DFS(v , x);
}
}
void go(int u , int p){
vis[u] = 1;
for(Node X : newG[u]){
int v = X.cmp , id = X.id , U = X.u , V = X.v;
if(v == p) continue;
// if(vis[v]) continue;
go(v , u);
sum[u] += sum[v];
//cout << sum[v] << endl;
if(sum[v] > 0){
//cout << edges[id].f << " edges[i].f " << v << " v "<< endl;
// cout << edges[id].f << " u " << edges[id].s << " v " << endl;
if(edges[id].f == V){
ans[id] = 'R';
// cout << edges[id].f << " edges[i].f " << endl;
}
else{
ans[id] = 'L';
}
}
if(sum[v] < 0){
// cout << edges[id].f << " u " << edges[id].s << " v " << endl;
// cout << edges[id].f << " edges[i].f " << u << " u " << endl;
if(edges[id].f == U) ans[id] = 'R'; else ans[id] = 'L';
}
}
// cout << sum[u] << " sum " << endl;
}
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for(int i = 0; i < m; ++i){
int u , v;
cin >> u >> v; --u; --v;
adj[u].emplace_back(v , i); adj[v].emplace_back(u , i);
edges[i].f = u; edges[i].s = v;
}
ini();
for(int i = 0; i < n; ++i){
if(!vis[i]) dfs(i , -1);
}
ini();
int cmp = 0;
for(int i = 0; i < n; ++i){
if(!vis[i]){
DFS(i , cmp);
cmp++;
}
}
//cerr << "pk";
//cerr << cmp << " C " << endl;
for(int i = 0; i < m; ++i){
int cu = comp[edges[i].f] , cv = comp[edges[i].s];
//cerr << cu << " cu " << cv << " cv " << endl;
if(bridges[i]){
newG[cu].push_back({cv , i , edges[i].f , edges[i].s});
newG[cv].push_back({cu , i , edges[i].s , edges[i].f});
}
}
int q;
cin >> q;
while(q--){
int u , v;
cin >> u >> v; --u; --v;
sum[comp[u]]++; sum[comp[v]]--;
}
ini();
// sort(most , most + cmp); reverse(most , most + cmp);
for(int i = 0; i < n; ++i){
if(!vis[comp[i]]) go(comp[i] , -1);
}
for(int i = 0; i < m; ++i)if(ans[i] != 'L' && ans[i] != 'R') ans[i] = 'B';
for(int i = 0; i < m; ++i) cout << ans[i];
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5504 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
