| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 66389 | Vahan | One-Way Streets (CEOI17_oneway) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<vector>
using namespace std;
int n,m,k,u[200000],fup[200000],tin[200000],time;
vector<pair<int,int> > g[200000],br,tr[200000];
char pa[200000];
int sz[200000],par[2000000],uxx[200000],ux[200000],ind[200000],parent[200000][22],tiin[200000],tout[200000],pp[200000];
void setcreate(int a)
{
sz[a]=1;
par[a]=a;
}
int findparent(int a)
{
if(par[a]==a)
return a;
return par[a]=findparent(par[a]);
}
void setunion(int a,int b)
{
a=findparent(a);
b=findparent(b);
if(a==b)
return;
if(sz[a]>=sz[b])
{
par[b]=a;
sz[a]+=sz[b];
}
if(sz[b]>sz[a])
{
par[a]=b;
sz[b]+=sz[a];
}
}
void dfs(int v,int p)
{
u[v]=1;
fup[v]=tin[v]=time++;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i].first;
int ham=g[v][i].second;
if(to==v)
{
pa[ham]='B';
continue;
}
if(p==to)
continue;
if(u[to]==1)
{
fup[v]=min(fup[v],tin[to]);
pa[ham]='B';
setunion(v,to);
}
else
{
dfs(to,v);
fup[v]=min(fup[v],fup[to]);
if(fup[to]>tin[v])
br.push_back(make_pair(v,i));
else
{
pa[ham]='B';
setunion(v,to);
}
}
}
}
void dfs1(int v,int p)
{
tiin[v]=time++;
u[v]=1;
parent[v][0]=p;
for(int i=1;i<=20;i++)
parent[v][i]=parent[parent[v][i-1]][i-1];
for(int i=0;i<tr[v].size();i++)
{
int to=tr[v][i].first;
int ham=tr[v][i].second;
if(to==p)
continue;
pp[to]=ham;
dfs1(to,v);
}
tout[v]=time++;
}
bool upper (int a, int b) {
return tiin[a] <= tiin[b] && tout[a] >= tout[b];
}
int lca (int a, int b) {
if (upper (a, b)) return a;
if (upper (b, a)) return b;
for (int i=20; i>=0; --i)
if (! upper (parent[a][i], b))
a = parent[a][i];
return parent[a][0];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
uxx[a]=b;
g[a].push_back(make_pair(b,i));
g[b].push_back(make_pair(a,i));
}
for(int i=1;i<=n;i++)
setcreate(i);
for(int i=1;i<=n;i++)
{
if(u[i]==0)
dfs(i,0);
}
for(int i=1;i<=n;i++)
ind[i]=findparent(i);
for(int i=0;i<br.size();i++)
{
int a=br[i].first,b=g[a][br[i].second].first,ham=g[a][br[i].second].second;
if(uxx[a]==b)
ux[ind[a]]=ind[b];
else
ux[ind[b]]=ind[a];
tr[ind[a]].push_back(make_pair(ind[b],ham));
tr[ind[b]].push_back(make_pair(ind[a],ham));
}
for(int i=1;i<=n;i++)
u[ind[i]]=0;
for(int i=1;i<=n;i++)
{
if(u[ind[i]]==0)
dfs1(ind[i],ind[i]);
}
cin>>k;
for(int i=1;i<=k;i++)
{
int a,b;
cin>>a>>b;
a=ind[a];
b=ind[b];
if(a==b)
continue;
int c=lca(a,b);
int e=a;
while(e!=c)
{
int ee=parent[e][0];
if(ux[e]==ee)
pa[pp[e]]='R';
else
pa[pp[e]]='L';
e=ee;
}
e=b;
while(e!=c)
{
int ee=parent[e][0];
if(ux[e]==ee)
pa[pp[e]]='L';
else
pa[pp[e]]='R';
e=ee;
}
}
for(int i=1;i<=m;i++)
cout<<pa[i];
cout<<endl;
return 0;
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/