oj.uz

Submission #897619

# Submission time Handle Problem Language Result Execution time Memory
897619 2024-01-03T13:39:39 Z LCJLY One-Way Streets (CEOI17_oneway) C++14
100 / 100
 273 ms 44116 KB 
#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);
		//show(d[index],d[index]);
		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});
	}
	
	for(int x=1;x<=n;x++){
		if(visited[x]) continue;
		dfs(x,-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);
		//show(ancestor,hold);
		
		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]);
		}
	}
	
	for(int x=1;x<=n;x++){
		if(visited2[x]) continue;
		dp(x,-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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19548 KB Output is correct
2 Correct 3 ms 19556 KB Output is correct
3 Correct 3 ms 19544 KB Output is correct
4 Correct 4 ms 19620 KB Output is correct
5 Correct 3 ms 19548 KB Output is correct
6 Correct 4 ms 19492 KB Output is correct
7 Correct 3 ms 19544 KB Output is correct
8 Correct 3 ms 19512 KB Output is correct
9 Correct 3 ms 19548 KB Output is correct
10 Correct 3 ms 19548 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19548 KB Output is correct
2 Correct 3 ms 19556 KB Output is correct
3 Correct 3 ms 19544 KB Output is correct
4 Correct 4 ms 19620 KB Output is correct
5 Correct 3 ms 19548 KB Output is correct
6 Correct 4 ms 19492 KB Output is correct
7 Correct 3 ms 19544 KB Output is correct
8 Correct 3 ms 19512 KB Output is correct
9 Correct 3 ms 19548 KB Output is correct
10 Correct 3 ms 19548 KB Output is correct
11 Correct 34 ms 30264 KB Output is correct
12 Correct 43 ms 32036 KB Output is correct
13 Correct 60 ms 36560 KB Output is correct
14 Correct 93 ms 39076 KB Output is correct
15 Correct 77 ms 39576 KB Output is correct
16 Correct 79 ms 37404 KB Output is correct
17 Correct 78 ms 39404 KB Output is correct
18 Correct 69 ms 37460 KB Output is correct
19 Correct 67 ms 40692 KB Output is correct
20 Correct 47 ms 34896 KB Output is correct
21 Correct 43 ms 34412 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19548 KB Output is correct
2 Correct 3 ms 19556 KB Output is correct
3 Correct 3 ms 19544 KB Output is correct
4 Correct 4 ms 19620 KB Output is correct
5 Correct 3 ms 19548 KB Output is correct
6 Correct 4 ms 19492 KB Output is correct
7 Correct 3 ms 19544 KB Output is correct
8 Correct 3 ms 19512 KB Output is correct
9 Correct 3 ms 19548 KB Output is correct
10 Correct 3 ms 19548 KB Output is correct
11 Correct 34 ms 30264 KB Output is correct
12 Correct 43 ms 32036 KB Output is correct
13 Correct 60 ms 36560 KB Output is correct
14 Correct 93 ms 39076 KB Output is correct
15 Correct 77 ms 39576 KB Output is correct
16 Correct 79 ms 37404 KB Output is correct
17 Correct 78 ms 39404 KB Output is correct
18 Correct 69 ms 37460 KB Output is correct
19 Correct 67 ms 40692 KB Output is correct
20 Correct 47 ms 34896 KB Output is correct
21 Correct 43 ms 34412 KB Output is correct
22 Correct 163 ms 40528 KB Output is correct
23 Correct 199 ms 38736 KB Output is correct
24 Correct 273 ms 38480 KB Output is correct
25 Correct 145 ms 44116 KB Output is correct
26 Correct 164 ms 40136 KB Output is correct
27 Correct 162 ms 38832 KB Output is correct
28 Correct 31 ms 26420 KB Output is correct
29 Correct 102 ms 35152 KB Output is correct
30 Correct 88 ms 35516 KB Output is correct
31 Correct 88 ms 35660 KB Output is correct
32 Correct 92 ms 38736 KB Output is correct