oj.uz

Submission #607492

# Submission time Handle Problem Language Result Execution time Memory
607492 2022-07-26T18:30:25 Z UncoolAnon One-Way Streets (CEOI17_oneway) C++14
0 / 100
 16 ms 21332 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); 
map<int,int> up[N],down[N]; 
map<pii,int> m,s; 
bool SET(int a, int b){
	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; 
}
void go(int a, int p,int dcnt,int ucnt){
	dcnt+=down[a][0]; 
	ucnt+=up[a][0]; 
	vis[a]=0; 
	//cout<<dcnt<<" "<<ucnt<<" "<<a<<endl; 
	for(int&x:adj[a]){
		if(vis[x]){
			dcnt+=down[a][x]; 
			ucnt+=up[a][x];
			if(dcnt&&ucnt){} 
			else if(dcnt||ucnt){
				if(dcnt){
					m[mp(a,x)]=1; 
					m[mp(x,a)]=-1; 
				} 
				else{
					m[mp(a,x)]=-1; 
					m[mp(x,a)]=1; 
				}
			}
			go(x,a,dcnt,ucnt); 
			dcnt-=down[a][x]; 
			ucnt-=up[a][x];
		}
	}
		dcnt+=down[a][0]; 
	ucnt+=up[a][0]; 
}
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); 
		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; 
		for(int i=1;i<=n;i++) vis[i]=1; 
		path.clear(); 
		launch(a,b); 
		for(int i=0;i+1<path.size();i++){
			m[mp(path[i],path[i+1])]=1; 
			m[mp(path[i+1],path[i])]=-1; 
		}
		/*int lc=lca(a,b) ; 
		if(lc!=a){
			up[lc][blca(a,b)]++; 
			up[a][0]--;
		}
		if(lc!=b){
			down[lc][blca(b,a)]++;
			down[b][0]--; 
		}*/
	}
	/*for(int i=1;i<=n;i++)
		if(vis[i]) 
			go(i,-1,0,0);*/
	for(pii&x:ed){
		if(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; 	
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   for(int i=0;i+1<path.size();i++){
      |               ~~~^~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20948 KB Output is correct
2 Correct 10 ms 21032 KB Output is correct
3 Correct 11 ms 21204 KB Output is correct
4 Correct 12 ms 21204 KB Output is correct
5 Correct 16 ms 21280 KB Output is correct
6 Correct 14 ms 21268 KB Output is correct
7 Correct 15 ms 21332 KB Output is correct
8 Correct 12 ms 21260 KB Output is correct
9 Incorrect 13 ms 21204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20948 KB Output is correct
2 Correct 10 ms 21032 KB Output is correct
3 Correct 11 ms 21204 KB Output is correct
4 Correct 12 ms 21204 KB Output is correct
5 Correct 16 ms 21280 KB Output is correct
6 Correct 14 ms 21268 KB Output is correct
7 Correct 15 ms 21332 KB Output is correct
8 Correct 12 ms 21260 KB Output is correct
9 Incorrect 13 ms 21204 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20948 KB Output is correct
2 Correct 10 ms 21032 KB Output is correct
3 Correct 11 ms 21204 KB Output is correct
4 Correct 12 ms 21204 KB Output is correct
5 Correct 16 ms 21280 KB Output is correct
6 Correct 14 ms 21268 KB Output is correct
7 Correct 15 ms 21332 KB Output is correct
8 Correct 12 ms 21260 KB Output is correct
9 Incorrect 13 ms 21204 KB Output isn't correct
10 Halted 0 ms 0 KB -