#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef int64_t ll;
//~ #define int ll
const int N = 1e5 + 5;
vector<int> edges[N], davka[N], qq[N];
vector<int> ss;
int a[N], b[N], fup[N];
int t, used[N], tin[N];
int cmp[N], cur, is[N];
void dfs(int u, int p = -1){
used[u] = 1;
tin[u] = fup[u] = ++t;
ss.push_back(u);
for(auto x : edges[u]){
if(x == p) continue;
int v = a[x] ^ b[x] ^ u;
if(used[v]){
fup[u] = min(fup[u], tin[v]);
} else {
dfs(v, x);
fup[u] = min(fup[u], fup[v]);
}
}
//~ cout<<u<<" "<<tin[u]<<" "<<fup[u]<<endl;
if(tin[u] == fup[u]){
int x; cur++;
do{
x = ss.back(); ss.pop_back();
cmp[x] = cur;
}while(x != u);
}
}
set<int> sub[N];
void dfs_stol(int u, int p = -1){
used[u] = 1;
for(auto x : davka[u]){
if(x == p) continue;
int v = cmp[a[x]] ^ cmp[b[x]] ^ u;
dfs_stol(v, x);
if(sub[v].size() > sub[u].size()) swap(sub[u], sub[v]);
for(auto el : sub[v]){
sub[u].insert(el);
}
sub[v].clear();
}
for(auto x : qq[u]){
if(sub[u].count(-x)){
sub[u].erase(-x);
} else {
sub[u].insert(x);
}
}
//~ cout<<u<<" : ";
//~ for(auto x : sub[u]) cout<<x<<" ";
//~ cout<<endl;
if(sub[u].empty() && ~p){
is[p] = 2;
} else if(~p) {
if(*sub[u].begin() < 0 && (*--sub[u].end()) > 0){
assert(false);
}
if(*sub[u].begin() > 0){
is[p] = (a[p] == u);
} else {
is[p] = (b[p] == u);
}
}
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
for(int i=0;i<m;i++){
cin>>a[i]>>b[i];
edges[a[i]].push_back(i);
edges[b[i]].push_back(i);
}
for(int i=1;i<=n;i++){
if(used[i]) continue;
dfs(i);
}
for(int i=1;i<=n;i++){
for(auto x : edges[i]){ int v = a[x] ^ b[x] ^ i;
if(cmp[i] != cmp[v]){
davka[cmp[i]].push_back(x);
} else {
is[x] = 2;
}
}
}
//~ for(int i=1;i<=n;i++){
//~ cout<<cmp[i]<<" ";
//~ } cout<<endl;
//~ for(int i=1;i<=cur;i++){
//~ for(auto x : davka[i]){
//~ int v = cmp[a[x]] ^ cmp[b[x]] ^ i;
//~ cout<<i<<" "<<v<<" "<<x<<endl;
//~ }
//~ }
int p; cin>>p;
for(int i=1;i<=p;i++){
int a, b; cin>>a>>b;
qq[cmp[a]].push_back(i);
qq[cmp[b]].push_back(-i);
}
memset(used, 0, sizeof used);
for(int i=1;i<=cur;i++){
if(used[i]) continue;
dfs_stol(i);
}
for(int i=0;i<m;i++){
if(is[i] == 0) cout<<"L";
if(is[i] == 1) cout<<"R";
if(is[i] == 2) cout<<"B";
} cout<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
25044 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
25044 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
16 ms |
25044 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
