oj.uz

Submission #435762

# Submission time Handle Problem Language Result Execution time Memory
435762 2021-06-23T17:10:22 Z CaroLinda Highway Tolls (IOI18_highway) C++14
100 / 100
 432 ms 12124 KB 
#include "highway.h"
#include <bits/stdc++.h>

#define sz(x) (int)(x.size())
#define ll long long
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define pii pair<int,int>
#define mk make_pair
#define all(x) x.begin(),x.end()
#define pb push_back

const int MAX = 90010 ;

using namespace std ;

int N , A , B , M ;
int group[MAX] ;
vector<int> toAsk , ans , toxic ;
vector<pii> adj[MAX] ;
int dist[2][MAX] ;
long long C ;

void bfsDist(int S, int idx )
{
	for(int i = 0  ; i < N ; i++ ) dist[idx][i] = M+10 ;
	dist[idx][S] = 0 ;

	vector<int> fila = {S} ;
	int ini = 0 ;

	while(ini < sz(fila))
	{
		int x = fila[ini++] ;

		for(auto e : adj[x])
		{
			if(dist[idx][e.ff] <= dist[idx][x]+1 ) continue ;
			dist[idx][e.ff] = dist[idx][x]+1 ;
			fila.pb(e.ff) ;			
		}

	}

}

void bfs(int S, int idx, int X )
{
	vector<int> fila = {S} , edge , edge2 ;
	int ini = 0 ;

	group[S] = -1 ;

	while(ini < sz(fila))
	{
		int x = fila[ini++] ;

		for(auto e : adj[x] ) 
		{
			if(group[e.ff] != idx  ) 
			{
				if( dist[idx][x]+1 == dist[idx][e.ff] ) edge2.pb(e.ss) ;
				continue ;
			}

			group[e.ff] = -1 ;
			fila.pb(e.ff) ;
			edge.pb(e.ss) ;
		}

	}

	int l = 0 , r = sz(edge)-1 , mid , best = sz(edge)-1 ;
	while(l <= r )
	{
		mid = (l+r)>>1 ;

		lp(i,0,M) toAsk[i] = 0 ;
		for(auto e : toxic ) toAsk[e] = 1 ;
		for(auto e : edge2 ) toAsk[e] = 1 ;
		for(int i = mid ; i < sz(edge) ; i++ ) toAsk[edge[i]] = 1 ;
		toAsk[X] = 0 ;

		if( ask(toAsk) == C )
		{
			best = mid-1 ;
			r = mid-1 ;
		}
		else l = mid+1 ;
	} 

	ans.pb(fila[best+1]) ;
}

void find_pair(int _N, vector<int> U, vector<int> V, int _A, int _B) 
{
	N = _N ;
	A = _A ;
	B = _B ;
	M = sz(U) ;

	for(int i = 0 ; i < M ; i++ )
		for(int j = 0 ; j < 2 ; j++ , swap(U[i] , V[i]))
			adj[U[i]].pb( mk(V[i],i) ) ;

	lp(i,0,M) toAsk.pb(0) ;

	C = ask(toAsk);

	int l = 0 , r = sz(U)-1 , mid , best = 0 ;
	while(l <= r )
	{
		mid = (l+r)>>1 ;
		
		for(int i = 0 ; i <= mid ; i++ ) toAsk[i] = 1 ;
		for(int i = mid+1 ; i < M ; i++ ) toAsk[i] = 0 ;

		if(ask(toAsk) != C ) 
		{
			best = mid ;
			r = mid-1 ;
		}
		else l = mid+1 ;
	}

	bfsDist( U[best] , 0 ) ;
	bfsDist( V[best] , 1 ) ;

	for(int i = 0 ; i < N ; i++ )
	{
		if( dist[0][i] == dist[1][i] ) group[i] = -1 ;
		else if( dist[0][i] > dist[1][i] ) group[i] = 1 ;
	}

	for(int i = 0 ; i < M ; i++ )
	{
		if( group[U[i]] != -1 && group[U[i]] == group[V[i]] ) continue ;
		if(i == best) continue ;
		toxic.pb(i) ;	
	}

	bfs(U[best] ,0 , best ) ;
	bfs(V[best] , 1  , best ) ;

	answer(ans[0] , ans[1]) ;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2428 KB Output is correct
2 Correct 2 ms 2376 KB Output is correct
3 Correct 2 ms 2376 KB Output is correct
4 Correct 2 ms 2424 KB Output is correct
5 Correct 2 ms 2420 KB Output is correct
6 Correct 2 ms 2376 KB Output is correct
7 Correct 2 ms 2376 KB Output is correct
8 Correct 2 ms 2424 KB Output is correct
9 Correct 2 ms 2376 KB Output is correct
10 Correct 2 ms 2376 KB Output is correct
11 Correct 3 ms 2376 KB Output is correct
12 Correct 2 ms 2376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2504 KB Output is correct
2 Correct 16 ms 3292 KB Output is correct
3 Correct 159 ms 9808 KB Output is correct
4 Correct 161 ms 9808 KB Output is correct
5 Correct 162 ms 9804 KB Output is correct
6 Correct 142 ms 10020 KB Output is correct
7 Correct 158 ms 9800 KB Output is correct
8 Correct 150 ms 9872 KB Output is correct
9 Correct 156 ms 9816 KB Output is correct
10 Correct 151 ms 9804 KB Output is correct
11 Correct 175 ms 8820 KB Output is correct
12 Correct 175 ms 9188 KB Output is correct
13 Correct 174 ms 9360 KB Output is correct
14 Correct 166 ms 9244 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3144 KB Output is correct
2 Correct 29 ms 3872 KB Output is correct
3 Correct 41 ms 4608 KB Output is correct
4 Correct 112 ms 8820 KB Output is correct
5 Correct 127 ms 8908 KB Output is correct
6 Correct 113 ms 9248 KB Output is correct
7 Correct 202 ms 9332 KB Output is correct
8 Correct 122 ms 8952 KB Output is correct
9 Correct 123 ms 9180 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2376 KB Output is correct
2 Correct 18 ms 3144 KB Output is correct
3 Correct 112 ms 8432 KB Output is correct
4 Correct 147 ms 9936 KB Output is correct
5 Correct 139 ms 9816 KB Output is correct
6 Correct 138 ms 9820 KB Output is correct
7 Correct 252 ms 9816 KB Output is correct
8 Correct 202 ms 9928 KB Output is correct
9 Correct 158 ms 9784 KB Output is correct
10 Correct 177 ms 9816 KB Output is correct
11 Correct 261 ms 9252 KB Output is correct
12 Correct 249 ms 9236 KB Output is correct
13 Correct 156 ms 9184 KB Output is correct
14 Correct 252 ms 8868 KB Output is correct
15 Correct 185 ms 9848 KB Output is correct
16 Correct 142 ms 9816 KB Output is correct
17 Correct 219 ms 9280 KB Output is correct
18 Correct 160 ms 9452 KB Output is correct
19 Correct 236 ms 9816 KB Output is correct
20 Correct 255 ms 9256 KB Output is correct
21 Correct 218 ms 10224 KB Output is correct
22 Correct 120 ms 10316 KB Output is correct
23 Correct 227 ms 9452 KB Output is correct
24 Correct 134 ms 9484 KB Output is correct
25 Correct 148 ms 9344 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3204 KB Output is correct
2 Correct 19 ms 3244 KB Output is correct
3 Correct 267 ms 10180 KB Output is correct
4 Correct 204 ms 10516 KB Output is correct
5 Correct 231 ms 12124 KB Output is correct
6 Correct 374 ms 11400 KB Output is correct
7 Correct 355 ms 11316 KB Output is correct
8 Correct 236 ms 11240 KB Output is correct
9 Correct 289 ms 9744 KB Output is correct
10 Correct 160 ms 10244 KB Output is correct
11 Correct 174 ms 10496 KB Output is correct
12 Correct 364 ms 10896 KB Output is correct
13 Correct 379 ms 11156 KB Output is correct
14 Correct 373 ms 11260 KB Output is correct
15 Correct 258 ms 11488 KB Output is correct
16 Correct 214 ms 10200 KB Output is correct
17 Correct 222 ms 10012 KB Output is correct
18 Correct 143 ms 10464 KB Output is correct
19 Correct 214 ms 10136 KB Output is correct
20 Correct 140 ms 10424 KB Output is correct
21 Correct 277 ms 11696 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3264 KB Output is correct
2 Correct 21 ms 3368 KB Output is correct
3 Correct 289 ms 9912 KB Output is correct
4 Correct 306 ms 10144 KB Output is correct
5 Correct 200 ms 10428 KB Output is correct
6 Correct 327 ms 11196 KB Output is correct
7 Correct 242 ms 10208 KB Output is correct
8 Correct 192 ms 10664 KB Output is correct
9 Correct 336 ms 10216 KB Output is correct
10 Correct 358 ms 11272 KB Output is correct
11 Correct 270 ms 11432 KB Output is correct
12 Correct 244 ms 11220 KB Output is correct
13 Correct 205 ms 10496 KB Output is correct
14 Correct 293 ms 9988 KB Output is correct
15 Correct 179 ms 10508 KB Output is correct
16 Correct 310 ms 9996 KB Output is correct
17 Correct 208 ms 10500 KB Output is correct
18 Correct 234 ms 10404 KB Output is correct
19 Correct 356 ms 10636 KB Output is correct
20 Correct 398 ms 11132 KB Output is correct
21 Correct 384 ms 11312 KB Output is correct
22 Correct 400 ms 11280 KB Output is correct
23 Correct 377 ms 11176 KB Output is correct
24 Correct 432 ms 11232 KB Output is correct
25 Correct 377 ms 11328 KB Output is correct
26 Correct 330 ms 11324 KB Output is correct
27 Correct 153 ms 10432 KB Output is correct
28 Correct 136 ms 10084 KB Output is correct
29 Correct 224 ms 10348 KB Output is correct
30 Correct 134 ms 10188 KB Output is correct
31 Correct 197 ms 10308 KB Output is correct
32 Correct 139 ms 10056 KB Output is correct
33 Correct 230 ms 10492 KB Output is correct
34 Correct 170 ms 10320 KB Output is correct
35 Correct 214 ms 10116 KB Output is correct
36 Correct 152 ms 10036 KB Output is correct
37 Correct 236 ms 10452 KB Output is correct
38 Correct 99 ms 10440 KB Output is correct
39 Correct 245 ms 11596 KB Output is correct
40 Correct 226 ms 11588 KB Output is correct
41 Correct 248 ms 11836 KB Output is correct
42 Correct 377 ms 11332 KB Output is correct