oj.uz

Submission #655842

# Submission time Handle Problem Language Result Execution time Memory
655842 2022-11-05T18:50:56 Z manizare One-Way Streets (CEOI17_oneway) C++14
60 / 100
 1115 ms 262144 KB 
#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define pb push_back
#define int long long
using namespace std ;

const int maxn = 3e5 + 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(long long 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 16 ms 33236 KB Output is correct
2 Correct 16 ms 33160 KB Output is correct
3 Correct 17 ms 33332 KB Output is correct
4 Correct 16 ms 33388 KB Output is correct
5 Correct 21 ms 33708 KB Output is correct
6 Correct 16 ms 33236 KB Output is correct
7 Correct 17 ms 33620 KB Output is correct
8 Correct 16 ms 33364 KB Output is correct
9 Correct 15 ms 33360 KB Output is correct
10 Correct 16 ms 33364 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33236 KB Output is correct
2 Correct 16 ms 33160 KB Output is correct
3 Correct 17 ms 33332 KB Output is correct
4 Correct 16 ms 33388 KB Output is correct
5 Correct 21 ms 33708 KB Output is correct
6 Correct 16 ms 33236 KB Output is correct
7 Correct 17 ms 33620 KB Output is correct
8 Correct 16 ms 33364 KB Output is correct
9 Correct 15 ms 33360 KB Output is correct
10 Correct 16 ms 33364 KB Output is correct
11 Correct 63 ms 42416 KB Output is correct
12 Correct 74 ms 43320 KB Output is correct
13 Correct 71 ms 44464 KB Output is correct
14 Correct 83 ms 45884 KB Output is correct
15 Correct 92 ms 46132 KB Output is correct
16 Correct 97 ms 46500 KB Output is correct
17 Correct 172 ms 74160 KB Output is correct
18 Correct 85 ms 46668 KB Output is correct
19 Correct 133 ms 77312 KB Output is correct
20 Correct 60 ms 42784 KB Output is correct
21 Correct 60 ms 42884 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 33236 KB Output is correct
2 Correct 16 ms 33160 KB Output is correct
3 Correct 17 ms 33332 KB Output is correct
4 Correct 16 ms 33388 KB Output is correct
5 Correct 21 ms 33708 KB Output is correct
6 Correct 16 ms 33236 KB Output is correct
7 Correct 17 ms 33620 KB Output is correct
8 Correct 16 ms 33364 KB Output is correct
9 Correct 15 ms 33360 KB Output is correct
10 Correct 16 ms 33364 KB Output is correct
11 Correct 63 ms 42416 KB Output is correct
12 Correct 74 ms 43320 KB Output is correct
13 Correct 71 ms 44464 KB Output is correct
14 Correct 83 ms 45884 KB Output is correct
15 Correct 92 ms 46132 KB Output is correct
16 Correct 97 ms 46500 KB Output is correct
17 Correct 172 ms 74160 KB Output is correct
18 Correct 85 ms 46668 KB Output is correct
19 Correct 133 ms 77312 KB Output is correct
20 Correct 60 ms 42784 KB Output is correct
21 Correct 60 ms 42884 KB Output is correct
22 Runtime error 1115 ms 262144 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -