oj.uz

Submission #655841

# Submission time Handle Problem Language Result Execution time Memory
655841 2022-11-05T18:49:34 Z manizare One-Way Streets (CEOI17_oneway) C++17
60 / 100
 1981 ms 262144 KB 
#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define pb push_back

using namespace std ;

const int maxn = 6e5 + 10 , maxq = 502 , inf = 1e9 , mod = 1e9+7 ;
vector <pair <int , int > > G[maxn] ;
vector <int>  l[maxn] ;
int dp[maxn] , mark2[maxn] , mark[maxn] , par[maxn]  , cnt = 1 ,c[maxn] , st[maxn] , en[maxn] , pr[maxn] , pp[maxn] , ans[maxn] , ok[maxn]; 
pair <int , int > ed[maxn] ;
void dfs(int v){ 
	mark[v] = 1;
	for(int i = 0; i < (int)G[v].size() ; i++){
		int u = G[v][i].first , id = G[v][i].second ;
		if(mark[u] == 1){
			if(mark2[id] == 0){
				dp[v] ++ ;
				dp[u] -- ;
				ans[id] = 3 ;
				mark2[id] = 1; 
			}
			continue ;
		}
		mark2[id] = 1;
		par[u] = id ;
		dfs(u) ;
		dp[v]+=dp[u];
	}
}

void dfs2(int v , int r){
	mark[v] = 1;
	c[v] = r ;
	for(int i = 0; i < (int)G[v].size() ; i++){
		int u = G[v][i].first , id = G[v][i].second ;
		if(mark[u] == 1)continue ;
		if(dp[u] == 0){
			cnt ++;
			//cout << v << " " << u << "<---\n";
			pr[cnt] = id ;
			pp[cnt] = r ;
			l[r].pb(cnt);
			dfs2(u , cnt);
		}else{
			dfs2(u , r);
		}
	}
}
vector <int> vv[maxn] , uu[maxn] ;
int sec = 1 ;
void dfs3(int v){
	mark[v] = 1;
	for(int i = 0 ;i < (int)l[v].size() ; i++){
		int u = l[v][i] ;
		dfs3(u);
	}
	if(pp[v] == 0)return ; 
	int ok = 0 ;
	vector <int> xx , yy ;
	sort(all(vv[v]));sort(all(uu[v]));
	while(vv[v].size() > 0 && uu[v].size() > 0){
		int vx = vv[v].back() , vz = uu[v].back() ;
		if(vx == vz){
			vv[v].pop_back();
			uu[v].pop_back();
		}else if(vx > vz){
			vv[pp[v]].pb(vx);
			xx.pb(vx);
			vv[v].pop_back();
		}else{
			yy.pb(vz);
			uu[pp[v]].pb(vz);
			uu[v].pop_back();
		}
	}
	while(vv[v].size() > 0){
		int vx = vv[v].back(); vv[v].pop_back();
		xx.pb(vx);
		vv[pp[v]].pb(vx);
	}
	while(uu[v].size() > 0){
		int vx = uu[v].back() ; uu[v].pop_back();
		yy.pb(vx);
		uu[pp[v]].pb(vx);
	}
	int id = pr[v]; 
	if(xx.size() == 0 && yy.size() ==0 ){
		ans[pr[v]] = 3 ;
	}else if (yy.size() == 0){
		if(c[ed[id].first] == v){
			ans[id] = 2 ; 
		}else{
			ans[id] = 1 ;
		}
	}else{
		if(c[ed[id].first] == v){
			ans[id] = 1 ;
		}else{
			ans[id] = 2 ;
		}
	}
	uu[v].clear();
	vv[v].clear();
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
	int n , m ;
	cin >> n >> m ;
	for(int i =1  ;i <= m ; i++){
		int v , u ;
		cin >> v >> u ;
		if(v==u){
			ans[i] = 3; 
			continue ;
		}
		G[v].pb({u,i});
		G[u].pb({v,i});
		ed[i] = {v , u} ;
	}
	for(int i = 1; i <= n ; i++){
		if(mark[i] == 1)continue ;
		dfs(i);
	}
	for(int i =1 ; i <= n ; i++){
		if(par[i] == 0)continue ;
		if(dp[i] >= 1){
			ans[par[i]] = 3 ;
		}
	}
	memset(mark , 0 , sizeof mark);
	memset(mark2 , 0 , sizeof mark2);
	vector <int> vec ;
	for(int i =1; i <= n ; i ++){
		if(mark[i] == 1)continue ;
		vec.pb(cnt);
		dfs2(i ,cnt ) ;
		cnt++;
	}
	memset(mark , 0 , sizeof mark);

	int q ;
	cin >> q ;
	while(q--){
		int v , u ;
		cin >> v >> u ;
		if(c[v] == c[u])continue ;
		vv[c[v]].pb(q);
		uu[c[u]].pb(q);
	}
	for(int i =0 ; i < (int)vec.size() ;i++){
		int u = vec[i]; 
		dfs3(u);
	}
	for(int i = 1 ; i <= m ; i++){
		if(ans[i] == 3){
			cout << "B";
		}
		if(ans[i] == 2){
			cout << "R";
		}
		if(ans[i] == 1){
			cout << "L" ;
		}
	}
	cout << endl;
}

Compilation message

oneway.cpp: In function 'void dfs3(int)':
oneway.cpp:59:6: warning: unused variable 'ok' [-Wunused-variable]
   59 |  int ok = 0 ;
      |      ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61296 KB Output is correct
2 Correct 28 ms 61316 KB Output is correct
3 Correct 29 ms 61396 KB Output is correct
4 Correct 29 ms 61500 KB Output is correct
5 Correct 29 ms 61720 KB Output is correct
6 Correct 29 ms 61472 KB Output is correct
7 Correct 35 ms 61604 KB Output is correct
8 Correct 34 ms 61524 KB Output is correct
9 Correct 30 ms 61388 KB Output is correct
10 Correct 29 ms 61448 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61296 KB Output is correct
2 Correct 28 ms 61316 KB Output is correct
3 Correct 29 ms 61396 KB Output is correct
4 Correct 29 ms 61500 KB Output is correct
5 Correct 29 ms 61720 KB Output is correct
6 Correct 29 ms 61472 KB Output is correct
7 Correct 35 ms 61604 KB Output is correct
8 Correct 34 ms 61524 KB Output is correct
9 Correct 30 ms 61388 KB Output is correct
10 Correct 29 ms 61448 KB Output is correct
11 Correct 61 ms 66856 KB Output is correct
12 Correct 69 ms 67660 KB Output is correct
13 Correct 76 ms 68748 KB Output is correct
14 Correct 95 ms 69700 KB Output is correct
15 Correct 90 ms 69960 KB Output is correct
16 Correct 90 ms 70000 KB Output is correct
17 Correct 151 ms 86308 KB Output is correct
18 Correct 97 ms 69964 KB Output is correct
19 Correct 134 ms 89320 KB Output is correct
20 Correct 70 ms 67328 KB Output is correct
21 Correct 70 ms 67156 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 61296 KB Output is correct
2 Correct 28 ms 61316 KB Output is correct
3 Correct 29 ms 61396 KB Output is correct
4 Correct 29 ms 61500 KB Output is correct
5 Correct 29 ms 61720 KB Output is correct
6 Correct 29 ms 61472 KB Output is correct
7 Correct 35 ms 61604 KB Output is correct
8 Correct 34 ms 61524 KB Output is correct
9 Correct 30 ms 61388 KB Output is correct
10 Correct 29 ms 61448 KB Output is correct
11 Correct 61 ms 66856 KB Output is correct
12 Correct 69 ms 67660 KB Output is correct
13 Correct 76 ms 68748 KB Output is correct
14 Correct 95 ms 69700 KB Output is correct
15 Correct 90 ms 69960 KB Output is correct
16 Correct 90 ms 70000 KB Output is correct
17 Correct 151 ms 86308 KB Output is correct
18 Correct 97 ms 69964 KB Output is correct
19 Correct 134 ms 89320 KB Output is correct
20 Correct 70 ms 67328 KB Output is correct
21 Correct 70 ms 67156 KB Output is correct
22 Runtime error 1981 ms 262144 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -