제출 #379730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
379730		errorgorn	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	449 ms	66972 KiB

oneway

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

#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

struct ufds{
	int p[100005];
	int r[100005];
	
	ufds(){
		for (int x=0;x<100005;x++){
			p[x]=x;
			r[x]=0;
		}
	}
	int par(int i){
		if (p[i]==i) return i;
		else return p[i]=par(p[i]);
	}
	void unions(int i,int j){
		i=par(i),j=par(j);
		if (i==j) return;
		if (r[i]<r[j]){
			p[i]=j;
		}
		else{
			p[j]=i;
			if (r[i]==r[j]) r[i]++;
		}
	}
} dsu;

int n,m,q;
vector<int> al[100005];
int counter=1;
int in[100005];
int low[100005];
bool vis[100005];
void dfs(int i,int p){
	vis[i]=true;
	in[i]=low[i]=counter++;
	
	bool fp=true;
	for (auto &it:al[i]){
		if (it==p && fp){
			fp=false;
			continue;
		}
		if (in[it]){
			dsu.unions(i,it);
			low[i]=min(low[i],in[it]);
		}
		else{
			dfs(it,i);
			if (low[it]<=in[i]) dsu.unions(i,it);
			low[i]=min(low[i],low[it]);
		}
	}
}

vector<iii> edges;
int component[100005];
vector<ii> tal[100005];
set<int> s[100005];

int ans[100005];

void dfs2(int i,int p){
	vis[i]=true;
	for (auto &it:tal[i]){
		if (it.fi==p) continue;
		
		dfs2(it.fi,i);
		
		int tt=it.se;
		if (tt<0) tt=~tt;
		if (!s[it.fi].empty()){
			int temp=*s[it.fi].begin();
			
			if ((temp<0) != (it.se<0)) ans[tt]=1;
			else ans[tt]=2;
		}
		
		if (sz(s[it.fi])>sz(s[i])) swap(s[i],s[it.fi]);
		
		for (auto &it:s[it.fi]){
			if (s[i].count(~it)) s[i].erase(~it);
			else s[i].insert(it);
		}
	}
	
	//cout<<"debug: "<<i<<endl;
	//for (auto &it:s[i]) cout<<it<<" "; cout<<endl;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>m;
	
	int a,b;
	rep(x,0,m){
		cin>>a>>b;
		
		al[a].pub(b);
		al[b].pub(a);
		edges.pub(iii(ii(a,b),x));
	}
	
	memset(vis,false,sizeof(vis));
	rep(x,1,n+1) if (!vis[x]) dfs(x,-1);
	
	rep(x,1,n+1) component[x]=dsu.par(x);
	//rep(x,1,n+1) cout<<component[x]<<" "; cout<<endl;
	
	for (auto &it:edges){
		a=component[it.fi.fi],b=component[it.fi.se];
		if (a!=b){
			tal[a].pub(ii(b,it.se));
			tal[b].pub(ii(a,~it.se));
		}
	}
	
	cin>>q;
	rep(x,0,q){
		cin>>a>>b;
		a=component[a],b=component[b];
		if (a!=b) s[a].insert(x),s[b].insert(~x);
	}
	
	memset(ans,-1,sizeof(ans));
	
	memset(vis,false,sizeof(vis));
	rep(x,1,n+1) if (!vis[component[x]]) dfs2(component[x],-1);
	
	rep(x,0,m){
		if (ans[x]==-1) cout<<"B";
		else if (ans[x]==1) cout<<"R";
		else cout<<"L";
	}
}

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