Submission #1187635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187635		PieArmy	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	1 ms	2624 KiB

oneway

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

struct DSU{
	int n;
	vector<int>par,siz;
	void init(int N){
		n=N+1;
		par.resize(n+1);iota(par.begin(),par.end(),0);
		siz.resize(n+1,1);
	}
	int get(int x){
		if(par[x]==x)return x;
		return par[x]=get(par[x]);
	}
	bool unite(int a,int b){
		a=get(a);
		b=get(b);
		if(a==b)return false;
		if(siz[a]<siz[b])swap(a,b);
		par[b]=a;
		siz[a]+=siz[b];
		return true;
	}
};

int n,m;
pair<int,int>edge[100023];
vector<pair<int,int>>komsu[100023];
int dep[100023];
int bin[100023][17];
int dp[100023][2];
vector<int>brid,roots;
int yon[100023];
DSU dsu;
int us[100023];

int dfs(int pos,int las){
	int mn=dep[pos];
	for(auto x:komsu[pos]){
		if(x.sc==las)continue;
		if(dep[x.fr]){
			mn=min(mn,dep[x.fr]);
			continue;
		}
		dep[x.fr]=dep[pos]+1;
		int y=dfs(x.fr,x.sc);
		if(y==0){
			yon[x.sc]=0;
			brid.pb(x.sc);
		}
		else mn=min(mn,y);
	}
	if(mn==dep[pos])return 0;
	return mn;
}

void dfs(int pos){
	for(int i=1;i<17;i++){
		bin[pos][i]=bin[bin[pos][i-1]][i-1];
	}
	for(auto x:komsu[pos]){
		if(x.fr==bin[pos][0])continue;
		bin[x.fr][0]=pos;
		dep[x.fr]=dep[pos]+1;
		dfs(x.fr);
	}
}

void solve(int pos,int las){
	for(auto x:komsu[pos]){
		if(x.sc==las)continue;
		solve(x.fr,x.sc);
		dp[pos][0]+=dp[x.fr][0];
		dp[pos][1]+=dp[x.fr][1];
	}
	if(bin[pos][0]==0)return;
	if(dp[pos][0]){
		if(pos==edge[las].fr){
			yon[las]|=1;
		}
		else yon[las]|=2;
	}
	if(dp[pos][1]){
		if(pos==edge[las].fr){
			yon[las]|=2;
		}
		else yon[las]|=1;
	}
}

int lca(int a,int b){
	if(dep[a]<dep[b])swap(a,b);
	for(int i=0;i<17;i++){
		if((dep[a]-dep[b])&(1<<i))a=bin[a][i];
	}
	if(a==b)return a;
	for(int i=17-1;i>=0;i--){
		if(bin[a][i]!=bin[b][i]){
			a=bin[a][i];
			b=bin[b][i];
		}
	}
	return bin[a][0];
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		yon[i]=3;
		cin>>edge[i].fr>>edge[i].sc;
		if(edge[i].fr==edge[i].sc)continue;
		komsu[edge[i].fr].pb({edge[i].sc,i});
		komsu[edge[i].sc].pb({edge[i].fr,i});
	}
	for(int i=1;i<=n;i++){
		if(dep[i]==0){
			dep[i]=1;
			dfs(i,0);
		}
		komsu[i].clear();
	}
	dsu.init(n);
	for(int i=1;i<=m;i++){
		if(yon[i]){
			dsu.unite(edge[i].fr,edge[i].sc);
		}
	}
	for(int i=1;i<=n;i++){
		us[i]=dsu.get(i);
	}
	for(int x:brid){
		edge[x].fr=us[edge[x].fr];
		edge[x].sc=us[edge[x].sc];
		komsu[edge[x].fr].pb({edge[x].sc,x});
		komsu[edge[x].sc].pb({edge[x].fr,x});
	}
	for(int i=1;i<=n;i++){
		if(bin[us[i]][0]==0){
			dfs(us[i]);
			roots.pb(us[i]);
		}
	}
	int p;cin>>p;
	for(int i=0;i<p;i++){
		int x,y;cin>>x>>y;
		x=us[x];y=us[y];
		int lc=lca(x,y);
		dp[x][0]++;
		dp[lc][0]--;
		dp[y][1]++;
		dp[lc][1]--;
	}
	for(int x:roots){
		solve(x,0);
	}
	for(int i=1;i<=m;i++){
		if(yon[i]==1)cout<<'R';
		else if(yon[i]==2)cout<<'L';
		else cout<<'B';
	}
}

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