#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define DEBUGMODE 1
#ifdef ONLINE_JUDGE
#define DEBUGMODE 0
#endif
#define cerr if(DEBUGMODE) cerr
#define DEBUG(a) if(DEBUGMODE) cout<<(a)<<endl
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPR(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define EACH(i,c) for(auto (i):c)
#define endl '\n'
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define LLM LONG_LONG_MAX
#define gcd __gcd
#define pb push_back
#define pm make_pair
#define MANY_TESTS ll ntests; cin>>ntests; for(ll test=1; test<=ntests; test++)
#define contains(a,b) ((a).find(b)!=(a).end())
#define INF 1e16
#define NINF -1e16
#define cinv(n,v) ll n; cin>>n; vl v(n); cin>>v;
#define fact(f,n) vl f={0}; for(ll i=0; i<n; i++) f.push_back(f[i]*(i+1));
#define codejamout(s) cout<<"Case #"<<test<<": "<<s<<"\n";
#define LOG(x) cerr<<"Line "<<__LINE__<<":"<<#x<<" = "<<x<<endl;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll,ll>> vpll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll MOD=1e9+7;
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << ";" << par.second << ")"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "["; REP(i, v.size()) out << v[i] << ", "; out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }
template<typename T>
pair<T, ll> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return {*it, it - v.begin()};}
template<typename T>
pair<T, ll> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return {*it, it - v.begin()};}
template<class T>
bool remin(T& a, const T& b){return (b<a?a=b,1:0);}
template<class T>
bool remax(T& a, const T& b){return (a<b?a=b,1:0);}
ll getbit(ll number, ll index){return (number & (1<<index))<<index;}
struct LCA{
vl enter, exit;
vvl jump, graph;
ll n;
vl seen;
ll timer;
LCA(vvl _graph, ll root=0){
graph=_graph;
n=graph.size();
enter.resize(n);
exit.resize(n);
jump.resize(n);
timer=0;
seen.resize(n,0);
dfs(root);
jump[root].push_back(root);
ll cn=n,i=0;
while(cn){
cn>>=1;
REP(j,n) jump[j].push_back(jump[jump[j][i]][i]);
i++;
}
}
void dfs(ll i){
enter[i]=timer;
timer++;
seen[i]=1;
EACH(j,graph[i]){
if(!seen[j]){
dfs(j);
jump[j].push_back(i);
}
}
exit[i]=timer;
timer++;
}
bool ispredcessor(ll parent, ll child){
return enter[parent]<=enter[child] && exit[parent]>=exit[child];
}
ll solve(ll a, ll b){
if(ispredcessor(a,b)) return a;
if(ispredcessor(b,a)) return b;
for(ll i=jump[a].size()-1; i>=0; i--){
if(!ispredcessor(jump[a][i],b)) a=jump[a][i];
}
return jump[a][0];
}
ll operator()(ll a, ll b){
return solve(a,b);
}
};
vector<vector<pll>> g;
vvl used;
vl res, top, t, te, from, to;
vector<bool> s;
ll n,m;
vpll edges;
ll cnt=0;
bool ispredcessor(int a, int b){return t[a]<=t[b] && te[a]>=te[b];}
void dfs(int u, int parent=-1){
t[u]=cnt++;
s[u]=1;
EACH(i,g[u]){
if(i.ff==parent) parent=-1;
else if(!s[i.ff]){
dfs(i.ff,u);
if(t[top[i.ff]]<=t[u]){
res[i.ss]=2;
}
if(t[top[i.ff]]<=t[top[u]]){
top[u]=top[i.ff];
}
used[u].pb(i.ff);
used[i.ff].pb(u);
}
else{
res[i.ss]=2;
if(t[i.ff]<=t[top[u]]){
top[u]=i.ff;
}
}
}
te[u]=cnt++;
}
void dfs2(int u, LCA& lca){
s[u]=1;
EACH(i,g[u]){
if(!s[i.ff]){
dfs2(i.ff, lca);
if(ispredcessor(lca.solve(from[i.ff],i.ff),from[u])) from[u]=lca.solve(from[i.ff],i.ff);
if(ispredcessor(lca.solve(to[i.ff],i.ff),to[u])) to[u]=lca.solve(to[i.ff],i.ff);
if(!ispredcessor(i.ff,from[i.ff]) && res[i.ss]==-1){
res[i.ss]=(make_pair(1+from[i.ff],i.ff+1)==edges[i.ss]);
}
else if(!ispredcessor(i.ff,to[i.ff]) && res[i.ss]==-1){
res[i.ss]=(make_pair(1+i.ff,to[i.ff]+1)==edges[i.ss]);
}
else res[i.ss]=2;
}
}
}
int main(){
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
cin>>n>>m;
edges.resize(m);
g.resize(n);
used.resize(n);
cin>>edges;
REP(i,m){
g[edges[i].ff-1].pb({edges[i].ss-1,i});
g[edges[i].ss-1].pb({edges[i].ff-1,i});
}
s.resize(n,0);
res.resize(m,-1);
t.resize(n);
te.resize(n);
REP(i,n) top.pb(i);
REP(i,n) from.pb(i);
REP(i,n) to.pb(i);
dfs(0);
LCA lca(used);
ll p;
cin>>p;
REP(i,p){
ll f,t;
cin>>f>>t;
f--;t--;
if(ispredcessor(lca.solve(f,t),from[f])) from[f]=lca.solve(f,t);
if(ispredcessor(lca.solve(f,t),to[t])) to[t]=lca.solve(f,t);
}
s.assign(n,0);
dfs2(0,lca);
EACH(i,res){
cout<<"RLB"[i];
}
cout<<endl;
return 0;
}
Compilation message
oneway.cpp: In member function 'void LCA::dfs(ll)':
oneway.cpp:18:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
18 | #define EACH(i,c) for(auto (i):c)
| ^
oneway.cpp:100:9: note: in expansion of macro 'EACH'
100 | EACH(j,graph[i]){
| ^~~~
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
18 | #define EACH(i,c) for(auto (i):c)
| ^
oneway.cpp:139:5: note: in expansion of macro 'EACH'
139 | EACH(i,g[u]){
| ^~~~
oneway.cpp: In function 'void dfs2(int, LCA&)':
oneway.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
18 | #define EACH(i,c) for(auto (i):c)
| ^
oneway.cpp:164:5: note: in expansion of macro 'EACH'
164 | EACH(i,g[u]){
| ^~~~
oneway.cpp: In function 'int main()':
oneway.cpp:18:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
18 | #define EACH(i,c) for(auto (i):c)
| ^
oneway.cpp:225:5: note: in expansion of macro 'EACH'
225 | EACH(i,res){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
