Submission #1124909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124909		nikolashami	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	481 ms	62324 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+4,LG=ceil(log2(N))+1;
vector<int>g[N],spn[N],up[N],X[N],Y[N];
multiset<int>upp[N];
set<array<int,2>>edges;
int n,m,p,par[N],dep[N],vis[N],mxX[N],mxY[N],mxB[N],tout[N],tin[N],ti;
int cale[LG][N];

void construct(int u){
	vis[u]=1;
	for(int v:g[u]){
		if(!vis[v]){
			par[v]=u;
			spn[u].push_back(v);
			spn[v].push_back(u);
			dep[v]=dep[u]+1;
			construct(v);
		}
	}
}

void makett(int u,int p=0){
	tin[u]=++ti;
	vis[u]=1;
	cale[0][u]=p;
  	for(int i=1;i<LG;++i) 
  		cale[i][u]=cale[i-1][cale[i-1][u]];
	for(int v:spn[u])
		if(!vis[v])
			makett(v,u);
	tout[u]=++ti;
}

bool iznad(int a,int b){
	return tin[a]<=tin[b]&&tout[b]<=tout[a];
}

int lca(int a,int b){
	if(iznad(a,b))
		return a;
  	if(iznad(b,a)) 
  		return b;
  	for(int i=LG-1;i>=0;--i){
    	if(!iznad(cale[i][b],a)&&cale[i][b])
    		b=cale[i][b];
  	}
  	return cale[0][b];
}

multiset<array<int,2>>back;
map<array<int,2>,char>sol;
vector<array<int,2>>o;

void dfs(int u){
	vis[u]=1;
	mxB[u]=1e9;
	for(int v:up[u]){
		if(mxB[u]==1e9||dep[v]<dep[mxB[u]])
			mxB[u]=v;
	}
	mxX[u]=1e9;
	for(int v:X[u]){
		if(!iznad(u,v)&&!iznad(v,u)){
			int nw=lca(u,v);
			if(mxX[u]==1e9||dep[mxX[u]]>dep[nw])
				mxX[u]=nw;
			continue;
		}
		if(dep[v]>dep[u])continue;
		if(mxX[u]==1e9||dep[mxX[u]]>dep[v])
			mxX[u]=v;
	}
	mxY[u]=1e9;
	for(int v:Y[u]){
		if(!iznad(u,v)&&!iznad(v,u)){
			int nw=lca(u,v);
			if(mxY[u]==1e9||dep[mxY[u]]>dep[nw])
				mxY[u]=nw;
			continue;
		}
		if(dep[v]>dep[u])continue;
		if(mxY[u]==1e9||dep[mxY[u]]>dep[v])
			mxY[u]=v;
	}
	for(int v:spn[u]){
		if(vis[v])
			continue;
		dfs(v);
		if(mxB[u]==1e9||(mxB[v]!=1e9&&dep[mxB[v]]<dep[mxB[u]]))mxB[u]=mxB[v];
		if(mxX[u]==1e9||(mxX[v]!=1e9&&dep[mxX[v]]<dep[mxX[u]]))mxX[u]=mxX[v];
		if(mxY[u]==1e9||(mxY[v]!=1e9&&dep[mxY[v]]<dep[mxY[u]]))mxY[u]=mxY[v];
	}
}

char get(int u,int v){
	if(back.find({u,v})!=back.end()){
		back.erase(back.find({u,v}));
		back.erase(back.find({v,u}));
		return'B';
	}
	if(!sol[{u,v}]&&!sol[{v,u}])return'B';
	if(v==par[u])return sol[{u,v}];
	else return (sol[{v,u}]=='R'?'L':sol[{v,u}]=='B'?'B':'R');
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>m;
    for(int i=0,u,v;i<m;++i){
    	cin>>u>>v;
    	o.push_back({u,v});
    	g[u].push_back(v);
    	g[v].push_back(u);
    	upp[u].insert(v);
    	upp[v].insert(u);
    	back.insert({u,v});
    	back.insert({v,u});
    }

    cin>>p;
   	for(int i=0,x,y;i<p;++i){
   		cin>>x>>y;
   		X[x].push_back(y);
   		Y[y].push_back(x);
   	}

   	for(int i=1;i<=n;++i){
   		if(!vis[i])
   			construct(i);
   	}

   	fill(vis,vis+N,0);

   	for(int i=1;i<=n;++i){
   		if(!vis[i])
   			makett(i);
   	}
   	
   	for(int i=1;i<=n;++i){
   		for(int j:spn[i]){
   			back.erase(back.find({i,j}));
   			upp[i].erase(upp[i].find(j));
   		}
   	}

   	tin[0]=-1e9;
   	tout[0]=1e9;

   	for(int i=1;i<=n;++i){
   		vector<int>toer;
   		for(int j:upp[i])
   			if(j!=i&&iznad(i,j))
   				toer.push_back(j);
   		for(int j:toer)
   			upp[i].erase(upp[i].find(j));
   	}

   	for(int i=1;i<=n;++i){
   		for(int j:upp[i])
   			up[i].push_back(j);
   	}

   	fill(vis,vis+N,0);

   	for(int i=1;i<=n;++i){
   		if(!vis[i])
   			dfs(i);
   	}

   	for(int i=2;i<=n;++i){
   		if(mxB[i]!=1e9&&dep[mxB[i]]<=dep[par[i]])
   			sol[{i,par[i]}]='B';
   		else if(mxX[i]!=1e9&&dep[mxX[i]]<=dep[par[i]])
   			sol[{i,par[i]}]='R';
   		else if(mxY[i]!=1e9&&dep[mxY[i]]<=dep[par[i]])
   			sol[{i,par[i]}]='L';
   		else
   			sol[{i,par[i]}]='B';
   	}

   	for(auto [u,v]:o)
   		cout<<get(u,v);
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40