#include<bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int range_rng(int l, int r)
{
return uniform_int_distribution<int>(l,r)(rng);
}
struct muchie
{
bool visited;
int u;
int ou;
int v;
int ov;
int cycles;
};
struct bruh
{
int to;
int id;
};
muchie edge[100005];
vector<bruh> nodes[100005];
vector<bruh> children[100005];
int inedge[100005];
int h[100005];
int p[100005];
int up[17][100005];
bool visited[100005];
void dfs(int node)
{
if (visited[node])
return;
visited[node]=1;
for (auto x : nodes[node])
{
if (!visited[x.to])
{
children[node].push_back(x);
edge[x.id].visited=1;
inedge[x.to]=x.id;
h[x.to]=h[node]+1;
p[x.to]=node;
dfs(x.to);
}
}
}
void pull(int node)
{
for (auto x : children[node])
{
pull(x.to);
edge[inedge[node]].cycles+=edge[x.id].cycles;
}
}
int timer;
int tin[100005];
int tout[100005];
void dfs2(int node)
{
timer++;
tin[inedge[node]]=timer;
for (auto x : children[node])
{
dfs2(x.to);
}
timer++;
tout[inedge[node]]=timer;
}
class AIB
{
public:
int aib[200005];
void update(int idx, int delta)
{
while (idx<=timer)
{
aib[idx]+=delta;
idx+=idx&(-idx);
}
}
void update(int l, int r, int delta)
{
update(l,delta);
///update(r+1,-delta);
}
int query(int idx)
{
int ans;
ans=0;
while(idx>0)
{
ans+=aib[idx];
idx-=idx&(-idx);
}
return ans;
}
} aib;
int jump(int node, int k)
{
int i;
for (i=0;i<=16;i++)
{
if (k&(1<<i))
node=up[i][node];
}
return node;
}
int lca(int a, int b)
{
int i,k;
if (h[a]<h[b])
swap(a,b);
k=h[a]-h[b];
a=jump(a,k);
if (a==b)
return a;
for (i=16;i>=0;i--)
{
if (up[i][a]!=up[i][b])
{
a=up[i][a];
b=up[i][b];
}
}
return up[0][a];
}
bool is_ancestor(int a, int b)
{
int k;
if (h[a]<h[b])
swap(a,b);
k=h[a]-h[b];
if (jump(a,k)!=b)
return 0;
return 1;
}
void configure_path(int from, int to)
{
if (is_ancestor(from,to))
{
aib.update(tin[inedge[to]],1);
aib.update(tin[inedge[from]],-1);
return;
}
if (is_ancestor(to,from))
{
aib.update(tin[inedge[from]],-1);
aib.update(tin[inedge[to]],1);
return;
}
int c;
c=lca(from,to);
aib.update(tin[inedge[from]],-1);
aib.update(tin[inedge[c]],1);
aib.update(tin[inedge[to]],1);
aib.update(tin[inedge[c]],-1);
}
signed main()
{
//ifstream fin("secvp.in");
//ofstream fout("secvp.out");
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m,i,j,u,v,from,to,req;
cin >> n >> m;
for (i=1; i<=m; i++)
{
cin >> u >> v;
nodes[u].push_back({v,i});
nodes[v].push_back({u,i});
edge[i].u=u;
edge[i].ou=u;
edge[i].v=v;
edge[i].ov=v;
edge[i].cycles=0;
edge[i].visited=0;
}
h[1]=1;
p[1]=1;
dfs(1);
for (i=1; i<=m; i++)
{
if (h[edge[i].u]<h[edge[i].v])
swap(edge[i].u,edge[i].v);
if (!edge[i].visited)
{
edge[i].cycles++;
edge[inedge[edge[i].u]].cycles++;
edge[inedge[edge[i].v]].cycles--;
}
}
pull(1);
for (i=1; i<=n; i++)
{
up[0][i]=p[i];
}
for (i=1; i<=16; i++)
{
for (j=1; j<=n; j++)
{
up[i][j]=up[i-1][up[i-1][j]];
}
}
dfs2(1);
cin >> req;
for (i=1; i<=req; i++)
{
cin >> u >> v;
configure_path(u,v);
}
string rez;
rez="";
for (i=1;i<=m;i++)
{
if (!edge[i].cycles)
{
if (aib.query(tout[i])-aib.query(tin[i]-1)>0)///sus->jos
{
if (edge[i].ou==edge[i].u)
{
rez+="L";
}
else
{
rez+="R";
}
}
else ///jos->sus
{
if (edge[i].ou==edge[i].u)
{
rez+="R";
}
else
{
rez+="L";
}
}
}
else
{
rez+="B";
}
}
cout << rez;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |