oj.uz

Submission #1058362

# Submission time Handle Problem Language Result Execution time Memory
1058362 2024-08-14T09:34:36 Z ReLice Highway Tolls (IOI18_highway) C++17
100 / 100
 142 ms 28820 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define vll vector<ll>
#define pb push_back
#define pf push_front
#define sz size()
#define bc back()
#define pob pop_back()
#define pof pop_front()
#define fr first
#define sc second
using namespace std;
const ll N=2e5+7;
const ll inf=1e18;
vector<vector<array<ll,2>>> g(N), g2(N);
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	ll M = V.sz;
	ll s, t, rt;
	ll n = N;
	vll v, u;
	ll i;
	
	for(auto i : V) v.pb(i);
	for(auto i : U) u.pb(i);
	
	vector<int> w(M, 0);
	
	ll x = ask(w);
	
	for(i=0;i<M;i++){
		g[v[i]].pb({u[i], i});
		g[u[i]].pb({v[i], i});
	}
	
	{//getting vertex on the path
		int l = 0, r = n - 1, ans;
	
		while ( l <= r ){
			int m = (l + r) / 2;
			
			if ( r - l > 60000 ) m = 60000;
			
			w.assign(M, 0);
			
			for ( int u = m + 1; u < n; u++ ){
				for ( auto &[v, j]: g[u] ){
					w[j] = 1;
				}
			}
			
			if ( ask(w) == x ){
				ans = m;
				r = m - 1;
			} else l = m + 1;
		}
		
		rt = ans;
	}
	
	vll p(n), d(n);
	vll pr(n), tour;
	vector<vll> dd(n);
	
	auto bfs = [&](ll s){
		for(i=0;i<n;i++){
			dd[i].clear();
			d[i] = inf;
			pr[i] = p[i] = -1;
		}
		
		queue<ll> q;
		q.push(s);
		d[s] = 0;
		
		while(q.size()){
			ll x = q.front();
			q.pop();
			
			dd[d[x]].pb(x);
			
			for(auto [to, r] : g[x]){
				if(d[to] > d[x] + 1){
					d[to] = d[x] + 1 ;
					pr[to] = r;
					p[to] = x;
					q.push(to);
				}
			}
		}
		
		tour.clear();
		for(i=0;i<n;i++){
			for(auto j : dd[i]) tour.pb(j);
		}
	};
	
	vll path;
	auto calc = [&](ll n){
		ll l = 0, r = n;
		while(l + 1 < r){
			ll m = (l + r) / 2;
			
			if(r - l > 60000) m = 60000;
			
			w.assign(M, 1);
			
			for(auto i : path) w[i] =0;
			
			//~ cout<<m<<endl;
			for(i=1;i<m;i++) {
				w[pr[tour[i]]] = 0;
				//~ cout<<v[pr[tour[i]]]<<' '<<u[pr[tour[i]]]<<endl;
			}
			
			ll y = ask(w);
				
			if(x == y) r = m;
			else l = m;
		}
		
		return r - 1;
	};
	
	bfs(rt);
	
	ll l = 1, r = n - 1;
	ll ans;
	
	while ( l <= r ){
		int m = (l + r) / 2;
		
		if ( r - l > 60000 ) m = 60000;
		
		w.assign(M, 1);
		
		for ( int i = 1; i <= m; i++ ){
			w[pr[tour[i]]] = 0;
		}
		
		if ( ask(w) == x ){
			ans = m;
			r = m - 1;
		} else l = m + 1;
	}
	
	s = tour[ans];
	
	{
		ll x = s;
		while(x != rt){
			path.pb(pr[x]);
			x = p[x];
		}
	}
	
	l = 0, r = ans - 1;
	
	while ( l <= r ){
		int m = (l + r) / 2;
		
		w.assign(M, 1);
		
		for ( auto &j: path ) w[j] = 0;
		
		for ( int i = 0; i < m; i++ ){
			w[pr[tour[i + 1]]] = 0;
		}
		
		if ( ask(w) == x ){
			ans = m;
			r = m - 1;
		} else l = m + 1;
	}
	
	t = tour[ans];
	
	answer(s, t);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:99:7: warning: variable 'calc' set but not used [-Wunused-but-set-variable]
   99 |  auto calc = [&](ll n){
      |       ^~~~
highway.cpp:147:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  147 |  s = tour[ans];
      |              ^
highway.cpp:58:6: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |   rt = ans;
      |   ~~~^~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10000 KB Output is correct
2 Correct 9 ms 11500 KB Output is correct
3 Correct 99 ms 24208 KB Output is correct
4 Correct 87 ms 24076 KB Output is correct
5 Correct 95 ms 24156 KB Output is correct
6 Correct 82 ms 24084 KB Output is correct
7 Correct 78 ms 24172 KB Output is correct
8 Correct 77 ms 24240 KB Output is correct
9 Correct 71 ms 24164 KB Output is correct
10 Correct 82 ms 24148 KB Output is correct
11 Correct 101 ms 24448 KB Output is correct
12 Correct 91 ms 24680 KB Output is correct
13 Correct 81 ms 24508 KB Output is correct
14 Correct 83 ms 24308 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11608 KB Output is correct
2 Correct 16 ms 13084 KB Output is correct
3 Correct 21 ms 14796 KB Output is correct
4 Correct 70 ms 24548 KB Output is correct
5 Correct 63 ms 24600 KB Output is correct
6 Correct 82 ms 25424 KB Output is correct
7 Correct 60 ms 25568 KB Output is correct
8 Correct 69 ms 24696 KB Output is correct
9 Correct 62 ms 25104 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10072 KB Output is correct
2 Correct 9 ms 11704 KB Output is correct
3 Correct 57 ms 21228 KB Output is correct
4 Correct 91 ms 24140 KB Output is correct
5 Correct 75 ms 24144 KB Output is correct
6 Correct 91 ms 24140 KB Output is correct
7 Correct 86 ms 24088 KB Output is correct
8 Correct 67 ms 24156 KB Output is correct
9 Correct 81 ms 24220 KB Output is correct
10 Correct 99 ms 24132 KB Output is correct
11 Correct 108 ms 24332 KB Output is correct
12 Correct 86 ms 24316 KB Output is correct
13 Correct 91 ms 24396 KB Output is correct
14 Correct 98 ms 24236 KB Output is correct
15 Correct 72 ms 24084 KB Output is correct
16 Correct 71 ms 24148 KB Output is correct
17 Correct 91 ms 24572 KB Output is correct
18 Correct 84 ms 24304 KB Output is correct
19 Correct 80 ms 24024 KB Output is correct
20 Correct 78 ms 24564 KB Output is correct
21 Correct 83 ms 24652 KB Output is correct
22 Correct 69 ms 24664 KB Output is correct
23 Correct 74 ms 24540 KB Output is correct
24 Correct 93 ms 24588 KB Output is correct
25 Correct 105 ms 24824 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11572 KB Output is correct
2 Correct 12 ms 11864 KB Output is correct
3 Correct 76 ms 25100 KB Output is correct
4 Correct 100 ms 26312 KB Output is correct
5 Correct 114 ms 28224 KB Output is correct
6 Correct 137 ms 28084 KB Output is correct
7 Correct 117 ms 28820 KB Output is correct
8 Correct 117 ms 28148 KB Output is correct
9 Correct 105 ms 21968 KB Output is correct
10 Correct 80 ms 22816 KB Output is correct
11 Correct 96 ms 24236 KB Output is correct
12 Correct 102 ms 27348 KB Output is correct
13 Correct 111 ms 27500 KB Output is correct
14 Correct 119 ms 28096 KB Output is correct
15 Correct 98 ms 28048 KB Output is correct
16 Correct 100 ms 24296 KB Output is correct
17 Correct 97 ms 24076 KB Output is correct
18 Correct 88 ms 24628 KB Output is correct
19 Correct 73 ms 24388 KB Output is correct
20 Correct 94 ms 24556 KB Output is correct
21 Correct 127 ms 28056 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11596 KB Output is correct
2 Correct 12 ms 11648 KB Output is correct
3 Correct 92 ms 25200 KB Output is correct
4 Correct 98 ms 25868 KB Output is correct
5 Correct 120 ms 26356 KB Output is correct
6 Correct 126 ms 28208 KB Output is correct
7 Correct 90 ms 25228 KB Output is correct
8 Correct 83 ms 25584 KB Output is correct
9 Correct 94 ms 26380 KB Output is correct
10 Correct 112 ms 28080 KB Output is correct
11 Correct 109 ms 28104 KB Output is correct
12 Correct 115 ms 28096 KB Output is correct
13 Correct 124 ms 24264 KB Output is correct
14 Correct 91 ms 22676 KB Output is correct
15 Correct 119 ms 24260 KB Output is correct
16 Correct 87 ms 22816 KB Output is correct
17 Correct 112 ms 24848 KB Output is correct
18 Correct 89 ms 22700 KB Output is correct
19 Correct 138 ms 26888 KB Output is correct
20 Correct 123 ms 27544 KB Output is correct
21 Correct 136 ms 28120 KB Output is correct
22 Correct 142 ms 28064 KB Output is correct
23 Correct 117 ms 28072 KB Output is correct
24 Correct 104 ms 28136 KB Output is correct
25 Correct 111 ms 28092 KB Output is correct
26 Correct 106 ms 28180 KB Output is correct
27 Correct 83 ms 24492 KB Output is correct
28 Correct 78 ms 24244 KB Output is correct
29 Correct 83 ms 24872 KB Output is correct
30 Correct 76 ms 24424 KB Output is correct
31 Correct 73 ms 24376 KB Output is correct
32 Correct 87 ms 24268 KB Output is correct
33 Correct 83 ms 25068 KB Output is correct
34 Correct 80 ms 24756 KB Output is correct
35 Correct 77 ms 24628 KB Output is correct
36 Correct 74 ms 24236 KB Output is correct
37 Correct 83 ms 24768 KB Output is correct
38 Correct 92 ms 24644 KB Output is correct
39 Correct 125 ms 27904 KB Output is correct
40 Correct 127 ms 27860 KB Output is correct
41 Correct 124 ms 28092 KB Output is correct
42 Correct 105 ms 28036 KB Output is correct