/*
IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;
#define SQ 350
#define endl '\n'
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define pf push_front
#define PQ priority_queue
#define size(x) ((ll)x.size())
#define DASH "---------"
#define UNDERLINE "_________"
#define all(x) (x).begin(),(x).end()
#define FORD(i, s, e) for(int i=s; i>=e; --i)
#define FOR(i, s, e) for(int i=s; i<=e; ++i)
#define kill(x) cout << x << '\n', exit(0);
#define set_dec(x) cout << fixed << setprecision(x);
#define ios ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x) cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
const int _N = 232323, _LG=131072, _lg=18;
const ll _MOD = 1e9+7; // 998244353
ll getmod(ll a, ll mod=_MOD) {return (a+3*mod)%mod;}
ll max(ll a, ll b) {return (a>b ? a : b);}
ll min(ll a, ll b) {return (a<b ? a : b);}
ll abso(ll a) {return (a<0?-a:a);}
int n, m, p, pref[_N][2], par[_N][_lg], low[_N], h[_N], mark[_N], ANS[_N];
vector<pii> adj[_N];
pii E[_N];
void addEdge(int ind) {
int v,u;
cin>>v>>u;
adj[v].pb({u, ind});
adj[u].pb({v, ind});
E[ind]={v, u};
}
void dfs(int v=1, int ind=0) {
low[v]=1e9, mark[v]=1;
FOR(i,1,_lg-1) {par[v][i]=par[par[v][i-1]][i-1];}
for(auto it2 : adj[v]) {
auto it = it2.F;
if(mark[it]==0) {
par[it][0]=v, h[it]=h[v]+1;
dfs(it, it2.S);
low[v]=min(low[it], low[v]);
} else if (it2.S!=ind) {
low[v]=min(h[it], low[v]);
}
}
}
int getPar(int v, int dist) {
while(dist>0) {
v=par[v][(int)log2(dist&-dist)];
dist-=(dist&-dist);
}
return v;
}
int getLCA(int v, int u) {
if(h[v]>h[u]) {swap(v,u);}
u=getPar(u, h[u]-h[v]);
if(v==u) {return v;}
FORD(i,_lg-1, 0) {
if(par[v][i]!=par[u][i]) {v=par[v][i], u=par[u][i];}
}
return par[v][0];
}
void partial(int v=1) {
mark[v]=1;
for(auto it : adj[v]) {
if(!mark[it.F]) {
partial(it.F);
pref[v][0]+=pref[it.F][0];
pref[v][1]+=pref[it.F][1];
if (low[it.F]>h[v] && (pref[it.F][0]!=0||pref[it.F][1]!=0)) {
ANS[it.S] = (pref[it.F][0]!=0 ? (E[it.S].F==it.F ? 1 : -1) : (E[it.S].F==v ? 1 : -1));
}
}
}
}
int main () {
ios;
cin>>n>>m;
FOR(i,1,m) {addEdge(i);}
// cout<<endl;
dfs();
fill(mark, mark+n+2, 0);
cin>>p;
FOR(i,1,p) {
int v,u,lca;
cin>>v>>u; // 0 -> up | 1 -> down
lca=getLCA(v,u);
if (lca==v) {
pref[u][1]++;pref[v][1]--;
} else if (lca==u) {
pref[v][0]++;pref[u][0]--;
} else {
pref[v][0]++;pref[u][1]++;pref[lca][0]--;pref[lca][1]--;
}
}
partial();
FOR(i,1,n) {
cout<<par[i][0]<<' ';
}
cout<<endl;
FOR(i,1,m) {
cout<<(ANS[i]==0 ? 'B' : (ANS[i]==1 ? 'R' : 'L'));
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
