oj.uz

Submission #655863

# Submission time Handle Problem Language Result Execution time Memory
655863 2022-11-05T19:40:26 Z manizare One-Way Streets (CEOI17_oneway) C++14
100 / 100
 136 ms 27128 KB 
#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define pb push_back
using namespace std ;

const int maxn = 1e5 + 2 , maxq = 502 , inf = 1e9 , mod = 1e9+7 ;
vector <pair <int , int > > G[maxn] ;
vector <int>  l[maxn] ;
int dp[maxn] ;
bool mark2[maxn] , mark[maxn] ;
int par[maxn]  , cnt = 1 ,c[maxn] , pr[maxn] , pp[maxn] , dis[maxn] ;
short ans[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);
			dis[cnt] = dis[r] + 1 ; 
			dfs2(u , cnt);
		}else{
			dfs2(u , r);
		}
	}
}
int bi[maxn][23] ;
set <pair <int , int > > s[maxn] ;
int sec = 1 ;
void dfs3(int v){
	for(int i =0 ; i < l[v].size() ; i++){
		int u = l[v][i]; 
		dfs3(u);
		dp[v] += dp[u] ;
	}
}

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);
	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);
	for(int i =1 ; i <= n ; i++)G[i].clear();
	memset(dp , 0 , sizeof dp);
	int q ;
	cin >> q ;
	while(q--){
		int v , u ;
		cin >> v >> u ;
		if(c[v] == c[u])continue ;
		v= c[v] , u = c[u] ;
		dp[v]++;
		dp[u]--;
	}
	for(int i =0 ; i < (int)vec.size() ;i++){
		int u = vec[i]; 
		dfs3(u);
	}
	for(int i =1; i < cnt ; i++){
		if(dp[i] == 0){
			if(pr[i] == 0)continue ;
			ans[pr[i]] =3 ;
			continue ;
		}
		int id = pr[i] ;
		if(dp[i] > 0){
			if(c[ed[id].first] == i){
				ans[id] = 2 ;
			}else{
				ans[id] = 1;
			}
		}else{
			if(c[ed[id].first] == i){
				ans[id] = 1 ;
			}else{
				ans[id] = 2;
			}
		}
	}
	for(int i = 1 ; i <= m ; i++){
		if(ans[i] == 0){
			cout << i << "<--\n";
		}
		if(ans[i] == 3){
			cout << "B";
			continue ;
		}
		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:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i =0 ; i < l[v].size() ; i++){
      |                 ~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10240 KB Output is correct
2 Correct 7 ms 10236 KB Output is correct
3 Correct 7 ms 10240 KB Output is correct
4 Correct 6 ms 10324 KB Output is correct
5 Correct 7 ms 10324 KB Output is correct
6 Correct 9 ms 10240 KB Output is correct
7 Correct 9 ms 10368 KB Output is correct
8 Correct 6 ms 10240 KB Output is correct
9 Correct 6 ms 10244 KB Output is correct
10 Correct 7 ms 10196 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10240 KB Output is correct
2 Correct 7 ms 10236 KB Output is correct
3 Correct 7 ms 10240 KB Output is correct
4 Correct 6 ms 10324 KB Output is correct
5 Correct 7 ms 10324 KB Output is correct
6 Correct 9 ms 10240 KB Output is correct
7 Correct 9 ms 10368 KB Output is correct
8 Correct 6 ms 10240 KB Output is correct
9 Correct 6 ms 10244 KB Output is correct
10 Correct 7 ms 10196 KB Output is correct
11 Correct 63 ms 15820 KB Output is correct
12 Correct 55 ms 16776 KB Output is correct
13 Correct 68 ms 17884 KB Output is correct
14 Correct 84 ms 18832 KB Output is correct
15 Correct 82 ms 18996 KB Output is correct
16 Correct 81 ms 18800 KB Output is correct
17 Correct 92 ms 21140 KB Output is correct
18 Correct 85 ms 18712 KB Output is correct
19 Correct 74 ms 22460 KB Output is correct
20 Correct 59 ms 16188 KB Output is correct
21 Correct 62 ms 15848 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10240 KB Output is correct
2 Correct 7 ms 10236 KB Output is correct
3 Correct 7 ms 10240 KB Output is correct
4 Correct 6 ms 10324 KB Output is correct
5 Correct 7 ms 10324 KB Output is correct
6 Correct 9 ms 10240 KB Output is correct
7 Correct 9 ms 10368 KB Output is correct
8 Correct 6 ms 10240 KB Output is correct
9 Correct 6 ms 10244 KB Output is correct
10 Correct 7 ms 10196 KB Output is correct
11 Correct 63 ms 15820 KB Output is correct
12 Correct 55 ms 16776 KB Output is correct
13 Correct 68 ms 17884 KB Output is correct
14 Correct 84 ms 18832 KB Output is correct
15 Correct 82 ms 18996 KB Output is correct
16 Correct 81 ms 18800 KB Output is correct
17 Correct 92 ms 21140 KB Output is correct
18 Correct 85 ms 18712 KB Output is correct
19 Correct 74 ms 22460 KB Output is correct
20 Correct 59 ms 16188 KB Output is correct
21 Correct 62 ms 15848 KB Output is correct
22 Correct 136 ms 23312 KB Output is correct
23 Correct 101 ms 21252 KB Output is correct
24 Correct 117 ms 20992 KB Output is correct
25 Correct 101 ms 27128 KB Output is correct
26 Correct 104 ms 22724 KB Output is correct
27 Correct 88 ms 21380 KB Output is correct
28 Correct 37 ms 14576 KB Output is correct
29 Correct 75 ms 17824 KB Output is correct
30 Correct 94 ms 17988 KB Output is correct
31 Correct 62 ms 18372 KB Output is correct
32 Correct 78 ms 21796 KB Output is correct