oj.uz

Submission #607520

# Submission time Handle Problem Language Result Execution time Memory
607520 2022-07-26T19:17:30 Z UncoolAnon One-Way Streets (CEOI17_oneway) C++14
100 / 100
 755 ms 61352 KB 
#include <bits/stdc++.h> 
 
 
#define pii pair<int,int> 
#define F first 
#define S second 
#define mp make_pair 
 
using namespace std; 
const int N=100001,lg=19;  
int tim=0; 
int sp[lg][N]; 
vector<int> adj[N],tin(N),tout(N),low(N),vis(N); 
int up[N],down[N]; 
map<pii,int> m,s; 
map<pii,int> cnt; 
bool SET(int a, int b){
	if(cnt[mp(a,b)]==1) s[mp(a,b)]=s[mp(b,a)]=1; 
	return 1; 
}
bool is_bridge(int a,int b){return s[mp(a,b)]; }
void dfs(int a, int p){
	vis[a]=1; 
	sp[0][a]=p; 
	for(int i=1;i<lg;i++)
		if(sp[i-1][a]!=-1)
			sp[i][a]=sp[i-1][sp[i-1][a]]; 
	tin[a]=++tim,low[a]=tim; 
	for(int&x:adj[a]){
			if(x==p) continue; 
			if(vis[x]) 
				low[a]=min(low[a],tin[x]); 
			else{
				dfs(x,a);
				low[a]=min(low[a],low[x]); 
				if(low[x]>tin[a]) SET(x,a); 
			}
	}
	tout[a]=++tim; 
	return ; 
}
int is_ancestor(int a, int b){
	return (tin[a]<=tin[b]&&tout[b]<=tout[a]); 
}
int lca(int a, int b){
	if(is_ancestor(a,b)) return a; 
	for(int i=lg-1;i>-1;--i)
		if(sp[i][a]!=-1&&!is_ancestor(sp[i][a],b))
			a=sp[i][a]; 
	return sp[0][a]; 
}
int blca(int a, int b){
	if(is_ancestor(a,b)) return -1;  
	for(int i=lg-1;i>-1;--i)
		if(sp[i][a]!=-1&&!is_ancestor(sp[i][a],b))
			a=sp[i][a]; 
	return a; 
}
pii go(int a, int p){
	vis[a]=0; 
	int upi=0,downi=0; 
	for(int&x:adj[a])
		if(vis[x]){
			pii da= go(x,a); 
			if(da.F) m[mp(x,a)]=1,m[mp(a,x)]=-1; 
			if(da.S) m[mp(x,a)]=-1,m[mp(a,x)]=1; 
			upi+=da.F; 
			downi+=da.S; 
		}
	upi+=up[a]; downi+=down[a]; 
	return mp(upi,downi); 
}
int main(){
	for(int i=0;i<lg;i++) for(int j=0;j<N;j++) sp[i][j]=-1; 
	int n,meme; 
	cin>>n>>meme;
	vector<pii> ed; 
	while(meme--){
		int a,b; 
		cin>>a>>b; 
		adj[a].push_back(b); 
		adj[b].push_back(a); 
		cnt[mp(a,b)]++; 
		cnt[mp(b,a)]++; 
		ed.push_back(mp(a,b)); 
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])
			dfs(i,-1); 
	int q; 
	cin>>q; 
	vector<int> path; 
	function<bool(int,int)> launch=[&](int a, int b){
		vis[a]=0; 
		path.push_back(a); 
		if(a==b) return 1; 
		for(int&x:adj[a])
			if(vis[x]&&launch(x,b))
				return 1; 
		path.pop_back(); 
		return 0; 
	}; 
	while(q--){
		int a,b;
		cin>>a>>b; 
		int lc=lca(a,b) ; 
		up[lc]--,up[a]++; 
		down[lc]--,down[b]++; 
	}
	for(int i=1;i<=n;i++)
		if(vis[i]) 
			go(i,-1);
	for(pii&x:ed){
		if(x.F!=x.S&&is_bridge(x.F,x.S)){
			if(m[x]==1)cout<<"R";  
			else if(m[x]==-1)cout<<"L"; 
			else cout<<"B"; 
		}
		else cout<<"B"; 
	}
	return 0; 	
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11604 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 6 ms 11940 KB Output is correct
4 Correct 7 ms 11940 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 6 ms 11860 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Correct 7 ms 11860 KB Output is correct
10 Correct 8 ms 11860 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11604 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 6 ms 11940 KB Output is correct
4 Correct 7 ms 11940 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 6 ms 11860 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Correct 7 ms 11860 KB Output is correct
10 Correct 8 ms 11860 KB Output is correct
11 Correct 245 ms 37220 KB Output is correct
12 Correct 264 ms 39312 KB Output is correct
13 Correct 349 ms 41864 KB Output is correct
14 Correct 428 ms 44732 KB Output is correct
15 Correct 470 ms 45328 KB Output is correct
16 Correct 636 ms 47364 KB Output is correct
17 Correct 589 ms 53004 KB Output is correct
18 Correct 547 ms 47884 KB Output is correct
19 Correct 509 ms 54780 KB Output is correct
20 Correct 276 ms 38708 KB Output is correct
21 Correct 257 ms 36656 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11604 KB Output is correct
2 Correct 6 ms 11604 KB Output is correct
3 Correct 6 ms 11940 KB Output is correct
4 Correct 7 ms 11940 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 6 ms 11860 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 8 ms 11988 KB Output is correct
9 Correct 7 ms 11860 KB Output is correct
10 Correct 8 ms 11860 KB Output is correct
11 Correct 245 ms 37220 KB Output is correct
12 Correct 264 ms 39312 KB Output is correct
13 Correct 349 ms 41864 KB Output is correct
14 Correct 428 ms 44732 KB Output is correct
15 Correct 470 ms 45328 KB Output is correct
16 Correct 636 ms 47364 KB Output is correct
17 Correct 589 ms 53004 KB Output is correct
18 Correct 547 ms 47884 KB Output is correct
19 Correct 509 ms 54780 KB Output is correct
20 Correct 276 ms 38708 KB Output is correct
21 Correct 257 ms 36656 KB Output is correct
22 Correct 707 ms 56988 KB Output is correct
23 Correct 664 ms 53824 KB Output is correct
24 Correct 755 ms 53668 KB Output is correct
25 Correct 631 ms 61352 KB Output is correct
26 Correct 752 ms 55756 KB Output is correct
27 Correct 746 ms 53736 KB Output is correct
28 Correct 116 ms 14680 KB Output is correct
29 Correct 381 ms 41340 KB Output is correct
30 Correct 374 ms 41392 KB Output is correct
31 Correct 431 ms 42012 KB Output is correct
32 Correct 426 ms 44596 KB Output is correct