#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define eb emplace_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 2e5 + 5, MAXN = 1e7 + 5;
const long long oo = 1e18 + 7, mod = 1e9 + 7;
int n, m, p;
vector<int> Adj[N];
int times[N], low[N];
int l[N], r[N];
map<ii, int> edges;
vector<ii> ques;
int sparse1[N][20], sparse2[N][20];
char ans[N];
int cntt = 0;
void dfs(int u, int p, int root){
cntt++;
times[u] = low[u] = cntt;
l[u] = cntt;
//vector<int> child;
for(auto v : Adj[u]){
if(!times[v]){
//child.pb(v);
dfs(v, u, root);
//cout << u << " " << v << "\n";
//cout << low[u] << " " << low[v] << " " << times[u] << " " << times[v] << "\n";
if(low[v] <= times[u]){
//cout << u << " " << v << "\n";
ans[edges[{min(u, v), max(u, v)}]] = 'B';
}
else low[u] = min(low[u], low[v]);
}
else if(v != p){
low[u] = min(low[u], times[v]);
ans[edges[{min(u, v), max(u, v)}]] = 'B';
}
}
r[u] = cntt;
}
void prep(){
for(int i = 1; i <= n; i++) sparse2[i][0] = oo;
for(auto it : ques){
int temp1 = it.fi, temp2 = it.se;
if(times[temp1] > times[temp2]) swap(times[temp1], times[temp2]);
sparse1[temp1][0] = max(sparse1[temp1][0], temp2);
sparse2[temp2][0] = min(sparse2[temp2][0], temp1);
}
for(int i = 1; i <= 18; i++){
for(int j = 1; (j + (1LL << i) - 1) <= n; j++){
sparse1[j][i] = max(sparse1[j][i - 1], sparse1[j + (1LL << (i - 1))][i - 1]);
sparse2[j][i] = min(sparse2[j][i - 1], sparse2[j + (1LL << (i - 1))][i - 1]);
}
}
}
int get_mx(int l, int r){
int k = log2(r - l + 1);
return max(sparse1[l][k], sparse1[r - (1LL << k) + 1][k]);
}
int get_mn(int l, int r){
int k = log2(r - l + 1);
return min(sparse2[l][k], sparse2[r - (1LL << k) + 1][k]);
}
map<ii, vector<int>> cnt;
void process(){
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
cnt[{min(x, y), max(x, y)}].pb(i);
}
for(auto it : cnt){
int x = it.fi.fi, y = it.fi.se;
if(x == y){
ans[it.se[0]] = 'B';
continue;
}
Adj[x].pb(y);
Adj[y].pb(x);
if(it.se.size() > 1){
for(auto it1 : it.se) ans[it1] = 'B';
continue;
}
edges[{min(x, y), max(x, y)}] = it.se[0];
}
cin >> p;
for(int i = 1; i <= p; i++){
int u, v;
cin >> u >> v;
ques.pb({u, v});
}
dfs(1, 1, 1);
prep();
for(auto it : edges){
if(ans[it.se] == 'B') continue;
int templ = max(l[it.fi.fi], l[it.fi.se]), tempr = min(r[it.fi.fi], r[it.fi.se]);
int temp1 = get_mx(templ, tempr), temp2 = get_mn(templ, tempr);
if(temp1 > tempr) ans[it.se] = (l[it.fi.fi] < l[it.fi.se] ? 'R' : 'L');
else if(temp2 < templ) ans[it.se] = (l[it.fi.fi] < l[it.fi.se] ? 'L' : 'R');
else ans[it.se] = 'B';
}
for(int i = 1; i <= m; i++) cout << ans[i];
}
signed main(){
ios_base::sync_with_stdio(0);
/*
#ifdef nqm
freopen("input.inp", "r", stdin);
freopen("output.out", "w", stdout);
#endif
#ifndef nqm
#endif
*/
process();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
5068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
