#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e5+5;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
vector<pair<int,int>> edge(nax);
vector<pair<int,int>> adj[nax];
string ans;
int depth[nax];
int parent[nax];
vector<pair<int,int>> tre[nax];
vector<int> low[nax];
vector<int> up[nax];
bool vis[nax];
int dp[nax];
void dfs(int x,int p){
vis[x]=true;
for(auto u:adj[x]){
if (u.se==p) continue;
if (vis[u.fi]){
if (depth[u.fi]>depth[x]) continue;
low[u.fi].pb(x);
up[x].pb(u.fi);
continue;
}
depth[u.fi]=depth[x]+1;
tre[x].pb(u);
tre[u.fi].pb({x,u.se});
dfs(u.fi,u.se);
}
return;
}
void trav(int x,int p){
dp[x]=up[x].size()-low[x].size();
for(auto u:tre[x]){
if (u.fi==p) continue;
trav(u.fi,x);
dp[x]+=dp[u.fi];
}
//cout <<x<<" "<<up[x].size()<<" "<<low[x].size()<<" "<<dp[x]<<endl;
if (dp[x]==0){
parent[x]=x;
}else parent[x]=p;
}
int find(int x){
if(x==parent[x]) return x;
return parent[x]=find(parent[x]);
}
int bj[nax][20];
void compute(int x,int p){
for (int i = 1; i < 20; ++i)
{
bj[x][i]=bj[bj[x][i-1]][i-1];
}
for(auto u:tre[x]){
if(u.fi==p) continue;
bj[u.fi][0]=x;
compute(u.fi,x);
}
return;
}
int jump(int x,int d){
for (int i = 19; i >= 0; --i)
{
if(d&(1<<i)) x=bj[x][i];
}
return x;
}
int lca(int x,int y){
if(depth[x]<depth[y]) swap(x,y);
x=jump(x,depth[x]-depth[y]);
if(x==y) return x;
for (int i = 19; i <= 0 ;--i)
{
if(bj[x][i]!=bj[y][i]){
x=bj[x][i];
y=bj[y][i];
}
}
return bj[x][0];
}
int main()
{
optimise;
int n,m;
cin>>n>>m;
for (int i = 0; i < m; ++i)
{
int x,y;
cin>>x>>y;
x--;y--;
edge[i]={x,y};
adj[x].pb({y,i});
adj[y].pb({x,i});
ans.pb('B');
}
for (int i = 0; i < n; ++i)
{
if(vis[i]) continue;
dfs(i,-1);
trav(i,-1);
compute(i,-1);
}
int q;
cin>>q;
for (int i = 0; i < q; i++)
{
int x,y;
cin>>x>>y;
x--;y--;
x=find(x);
y=find(y);
int z=lca(find(x),find(y));
z=find(z);
while(find(x)!=z){
x=find(x);
for(auto u:adj[x]){
if(u.fi==bj[x][0]){
ans[u.se]=(edge[u.se].fi==u.fi ? 'L' : 'R');
parent[x]=u.fi;
}
}
}
while(find(y)!=z){
y=find(y);
for(auto u:adj[y]){
if(u.fi==bj[y][0]){
ans[u.se]=(edge[u.se].fi==u.fi ? 'R' : 'L');
parent[y]=u.fi;
}
}
}
}
cout <<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
4 ms |
10584 KB |
Output is correct |
| 3 |
Correct |
5 ms |
10660 KB |
Output is correct |
| 4 |
Execution timed out |
3099 ms |
10844 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
4 ms |
10584 KB |
Output is correct |
| 3 |
Correct |
5 ms |
10660 KB |
Output is correct |
| 4 |
Execution timed out |
3099 ms |
10844 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
4 ms |
10584 KB |
Output is correct |
| 3 |
Correct |
5 ms |
10660 KB |
Output is correct |
| 4 |
Execution timed out |
3099 ms |
10844 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
