oj.uz

Submission #607510

# Submission time Handle Problem Language Result Execution time Memory
607510 2022-07-26T18:57:45 Z UncoolAnon One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 63388 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; 
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; 
}
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); 
		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; 
		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(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; 	
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20948 KB Output is correct
2 Correct 10 ms 20948 KB Output is correct
3 Correct 12 ms 21280 KB Output is correct
4 Correct 12 ms 21332 KB Output is correct
5 Correct 18 ms 21388 KB Output is correct
6 Correct 13 ms 21176 KB Output is correct
7 Correct 15 ms 21440 KB Output is correct
8 Correct 14 ms 21344 KB Output is correct
9 Correct 12 ms 21332 KB Output is correct
10 Correct 13 ms 21180 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20948 KB Output is correct
2 Correct 10 ms 20948 KB Output is correct
3 Correct 12 ms 21280 KB Output is correct
4 Correct 12 ms 21332 KB Output is correct
5 Correct 18 ms 21388 KB Output is correct
6 Correct 13 ms 21176 KB Output is correct
7 Correct 15 ms 21440 KB Output is correct
8 Correct 14 ms 21344 KB Output is correct
9 Correct 12 ms 21332 KB Output is correct
10 Correct 13 ms 21180 KB Output is correct
11 Correct 804 ms 50012 KB Output is correct
12 Correct 1048 ms 52320 KB Output is correct
13 Correct 1740 ms 55828 KB Output is correct
14 Correct 1589 ms 57520 KB Output is correct
15 Correct 1686 ms 58052 KB Output is correct
16 Correct 561 ms 57048 KB Output is correct
17 Correct 1688 ms 63188 KB Output is correct
18 Correct 764 ms 57268 KB Output is correct
19 Correct 2202 ms 63388 KB Output is correct
20 Correct 1275 ms 52952 KB Output is correct
21 Correct 849 ms 46232 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20948 KB Output is correct
2 Correct 10 ms 20948 KB Output is correct
3 Correct 12 ms 21280 KB Output is correct
4 Correct 12 ms 21332 KB Output is correct
5 Correct 18 ms 21388 KB Output is correct
6 Correct 13 ms 21176 KB Output is correct
7 Correct 15 ms 21440 KB Output is correct
8 Correct 14 ms 21344 KB Output is correct
9 Correct 12 ms 21332 KB Output is correct
10 Correct 13 ms 21180 KB Output is correct
11 Correct 804 ms 50012 KB Output is correct
12 Correct 1048 ms 52320 KB Output is correct
13 Correct 1740 ms 55828 KB Output is correct
14 Correct 1589 ms 57520 KB Output is correct
15 Correct 1686 ms 58052 KB Output is correct
16 Correct 561 ms 57048 KB Output is correct
17 Correct 1688 ms 63188 KB Output is correct
18 Correct 764 ms 57268 KB Output is correct
19 Correct 2202 ms 63388 KB Output is correct
20 Correct 1275 ms 52952 KB Output is correct
21 Correct 849 ms 46232 KB Output is correct
22 Execution timed out 3056 ms 59696 KB Time limit exceeded
23 Halted 0 ms 0 KB -