#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define rep(i, a, b) for(ll i = a; i < ll(b); ++i)
#define rrep(i, a, b) for(ll i = b-1; i >= ll(a); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
ll n,m,p;
vector<pii> d;
vector<vector<pii>> e;
vector<pii> edges;
vi dfsnum;
vi dfslow;
vector<bool> seen;
ll c = 0;
vector<vi> adj;
ll dfs3(ll v, ll le){
if(seen[v]) return dfslow[v];
seen[v] = true;
dfsnum[v] = dfslow[v] = c++;
if(le!=-1){
//cout<<"tree edge "<< edges[le].first<<" "<<edges[le].second<<endl;
adj[edges[le].first].push_back(edges[le].second);
adj[edges[le].second].push_back(edges[le].first);
}
trav(up,e[v]){
ll u,ed;
tie(u,ed) = up;
if(ed==le) continue;
//cout<<v<<": "<<u<<endl;
dfslow[v] = min(dfslow[v], dfs3(u,ed));
}
//cout<<v<<": "<<dfsnum[v]<<" "<<dfslow[v]<<endl;
return dfslow[v];
}
vi height, par, visited;
vector<pii> u;
vector<vi> jump;
map<pii, ll> r;
void dfs(ll v, ll h, ll p){
height[v] = h;
par[v] = p;
for(ll x : adj[v]){
if(x != p) dfs(x, h+1, v);
}
}
pii dfs2(ll v){
//cout<<v<<endl;
visited[v] = 1;
pii h = u[v];
for(ll x : adj[v]){
//cout<<"x "<<x<<endl;
if(x != par[v]) h = min(h, dfs2(x));
}
if(h.first < height[v]){
//cout<<par[v]<<" "<< v<<" "<<h.second<<endl;
r[{par[v], v}] = h.second;
r[{v, par[v]}] = !h.second;
}
return h;
}
ll goup(ll from, ll steps){
for(ll i = 0; i < 20; i++){
if(steps&(1<<i)) from = jump[from][i];
if(from==-1) return -1;
}
return from;
}
ll lca(ll a, ll b){
if(height[a] < height[b]) swap(a, b);
//cout<<"heights: "<<height[a]<<" "<<height[b]<<endl;
//cout<<a<<" "<<b<<endl;
a = goup(a, height[a]-height[b]);
for(ll i = 19; i >= 0; i--){
//cout<<a<<" "<<b<<endl;
ll ta = jump[a][i];
ll tb = jump[b][i];
if(ta != tb) a=ta, b=tb;
}
return par[a];
}
void solvetree(){
height = visited = vi(n);
u = vector<pii>(n, {INT32_MAX, 0});
par = vi(n, -2);
for(ll i = 0; i < n; i++) if(par[i] == -2) dfs(i, 0, -1);
//cout<<"adj:"<<endl;
/*trav(us,adj) {
trav(u,us) //cout<<u<<" ";
//cout<<endl;
}*/
//cout<<"h:"<<endl;
trav(h,height) //cout<<h<<endl;
jump = vector<vi>(n, vi(20));
for(ll i = 0; i < n; i++){
jump[i][0] = par[i];
}
for(ll i = 1; i < 20; i++){
for(ll j = 0; j < n; j++){
jump[j][i] = jump[j][i-1]==-1?-1:jump[jump[j][i-1]][i-1];
}
}
for(ll i = 0; i < p; i++){
ll a = d[i].first;
ll b = d[i].second;
ll l = lca(a, b);
u[a] = {l, 1};
u[b] = {l, 0};
}
for(ll i = 0; i < n; i++){
if(!visited[i]) dfs2(i);
}
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
cin>>n>>m;
e.resize(n);
adj.resize(n);
rep(i,0,m) {
ll a,b;
cin>>a>>b;
--a;--b;
edges.emplace_back(a,b);
e[a].emplace_back(b,i);
e[b].emplace_back(a,i);
//cout<<"edge "<<a<<" "<<b<<endl;
}
cin>>p;
d.resize(p);
rep(i,0,p) {
ll a,b;
cin>>a>>b;
--a;--b;
d[i] = {a,b};
}
dfsnum.resize(n);
dfslow.resize(n);
seen.resize(n);
rep(i,0,n)
dfs3(i,-1);
vi bridges;
rep(i,0,m){
ll a,b;
tie(a,b) = edges[i];
if(dfsnum[a]>dfsnum[b]) swap(a,b);
if(dfslow[b]==dfsnum[b]){
bridges.push_back(i);
//cout<<"bridge: "<<a<<" "<<b<<endl;
}
}
solvetree();
string ans(m,'B');
trav(b,bridges){
pair<ll,ll> ed = edges[b];
if(r.find(ed)!=r.end())
ans[b] = "RL"[r[ed]];
}
cout<<ans<<endl;
}
Compilation message
oneway.cpp: In function 'void solvetree()':
oneway.cpp:115:10: warning: unused variable 'h' [-Wunused-variable]
115 | trav(h,height) //cout<<h<<endl;
| ^
oneway.cpp:8:30: note: in definition of macro 'trav'
8 | #define trav(a, x) for(auto& a : x)
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
