#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
constexpr int INF = 0x3f3f3f3f; constexpr ll LLINF = 0x3f3f3f3f3f3f3f3f;
#define db(x) { cerr << #x << " = " << x << endl; }
template <typename T> void _dbarr(T* a, size_t sz){ for(int i = 0; i < sz; i++) cerr << a[i] << " \n"[i == sz-1]; }
template <typename T> void _dbarr(vector<T> a, size_t sz){ for(int i = 0; i < sz; i++) cerr << a[i] << " \n"[i == sz-1]; }
#define dbarr(x, n) {cerr << #x << ": "; _dbarr((x),(n));}
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define mpr make_pair
#define fs first
#define sn second
const int MM = 1e5+5;
int n,m,p,disc[MM],ti,comp[MM],cid,diff[MM],low[MM];
char ans[MM];
vector<pi> adj[MM],adj1[MM];
bool vis[MM],vis1[MM];
vector<int> st;
void go(int u){
low[u] = disc[u] = ++ti;
st.eb(low[u]);
for(auto&[v,i]:adj[u]){
i >>= 1;
if(!vis[i]){
vis[i] = 1;
if(!disc[v]) {go(v); low[u] = min(low[u],low[v]); }
else low[u] = min(low[u],disc[v]);
}
}
if(low[u] == disc[u]){
cid++;
int x;
do{
x = st.back(); st.pop_back();
comp[x] = cid;
} while(x != u);
}
}
void dfs(int u, int p){
vis1[u] = 1;
for(auto&[v,i]:adj1[u]){
if(v == p) continue;
dfs(v,u);
diff[u] += diff[v];
if(diff[v]<0) ans[i>>1] = (i&1 ? 'R' : 'L');
else if(diff[v]>0) ans[i>>1] = (!(i&1) ? 'R' : 'L');
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
//freopen("in.txt","r", stdin);
cin >> n >> m;
for(int i = 0,j=0; i < m; i++){
int a,b;
cin >> a >> b; ans[i] = 'B';
adj[a].pb({b,j++}); adj[b].pb({a,j++});
}
for(int i = 1; i <= n; i++){
if(!disc[i])
go(i);
}
for(int i = 1; i <= n; i++)
for(auto& [j,k] : adj[i])
if(comp[i] != comp[j])
adj1[comp[i]].pb({comp[j],k});
cin >> p;
for(int i = 0; i < p; i++){
int a,b;
cin >> a >> b;
diff[comp[a]]++;
diff[comp[b]]--;
}
//for(int i = 1; i <= cid; i++) cout << i << " " << diff[i] << "\n";
for(int i = 1; i <= cid; i++)
if(!vis1[i])
dfs(i,0);
cout << ans << "\n";
//for(int i = 1; i <= n; i++) cout << i << " " << comp[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9984 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9984 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9984 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
