Submission #897485

#	Time	Username	Problem	Language	Result	Execution time	Memory
897485		LCJLY	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	3 ms	21596 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;

int n,m;
pii edge[100005];
vector<pii>adj[100005];
bool visited[100005];
bool self[100005];
int in[100005];
int low[100005];
int ptr=0;
bool bridge[100005];
int dir[100005];
int two[25][100005];
int d[100005];

void dfs(int index, int par){
	//show(index,index);
	in[index]=ptr;
	low[index]=ptr;
	ptr++;
	visited[index]=true;
	for(int x=0;x<20;x++){
		two[x+1][index]=two[x][two[x][index]];
	}
	for(auto it:adj[index]){
		if(!visited[it.first]){
			two[0][it.first]=index;
			d[it.first]=d[index]+1;
			dfs(it.first,it.second);
			if(low[it.first]>in[index]){
				bridge[it.second]=true;
			}
			low[index]=min(low[index],low[it.first]);
		}
		else if(it.second!=par){
			low[index]=min(low[index],in[it.first]);
		}
	}
}

int lca(int a, int b){
	if(d[a]>d[b]) swap(a,b);
	int diff=d[b]-d[a];
	for(int x=0;x<20;x++){
		if(diff&(1<<x)) b=two[x][b];
	}
	
	if(a==b) return a;
	
	for(int x=19;x>=0;x--){
		if(two[x][a]!=two[x][b]){
			a=two[x][a];
			b=two[x][b];
		}
	}
	return two[0][a];
}

int up[100005];
int down[100005];
int visited2[100005];

pii storage[100005];

void dp(int index, int par){
	visited2[index]=true;
	storage[index]={up[index],down[index]};
	for(auto it:adj[index]){
		if(!visited2[it.first]){
			dp(it.first,it.second);
			storage[index].first=min(storage[index].first,storage[it.first].first);
			storage[index].second=min(storage[index].second,storage[it.first].second);
		}
	}	
	
	if(par!=-1&&bridge[par]){
		//show3(par,par,storage[index].first,storage[index].first,storage[index].second,storage[index].second);
		if(storage[index].first<d[index]){
			dir[par]=index;
		}
		if(storage[index].second<d[index]){
			dir[par]=-index;
		}
	}
}

void solve(){	
	cin >> n >> m;
	
	int temp,temp2;
	for(int x=0;x<m;x++){
		cin >> temp >> temp2;
		edge[x]={temp,temp2};
		if(temp==temp2){
			self[x]=true;
			continue;
		}
		adj[temp].push_back({temp2,x});
		adj[temp2].push_back({temp,x});
	}
	
	dfs(1,-1);
	memset(dir,0,sizeof(dir));
	
	for(int x=1;x<n;x++){
		up[x]=d[x];
		down[x]=d[x];
	}
	
	int q;
	cin >> q;
	
	for(int x=0;x<q;x++){
		cin >> temp >> temp2;
		int hold=lca(temp,temp2);
		
		if(hold==temp){
			//down path
			down[temp2]=min(down[temp2],d[temp]);
		}
		else if(hold==temp2){
			//up path
			up[temp]=min(up[temp],d[temp2]);
		}
		else{
			//up down
			up[temp]=min(up[temp],d[hold]);
			down[temp2]=min(down[temp2],d[hold]);
		}
	}
	
	dp(1,-1);
	
	for(int x=0;x<m;x++){
		if(self[x]){
			cout << "B";
		}
		else if(!bridge[x]){
			cout << "B";
		}
		else{
			if(dir[x]==0){
				cout << "B";
			}
			else if(dir[x]>0){
				if(edge[x].first==dir[x]) cout << "R";
				else cout << "L";
			}
			else{
				if(edge[x].first==-dir[x]) cout << "L";
				else cout << "R";
			}
		}
	}
}
 
int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	//freopen("tribool.in", "r", stdin);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}	
}

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