oj.uz

Submission #1058067

# Submission time Handle Problem Language Result Execution time Memory
1058067 2024-08-14T08:13:35 Z ReLice Highway Tolls (IOI18_highway) C++17
90 / 100
 145 ms 28412 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
		ll l = 0, r = n;
		while(l + 1 < r){
			ll m = (l + r) / 2;
			
			if(r - l > 60000) m = 60000;
			
			w.assign(M, 0);
			
			for(i=0;i<m;i++){
				for(auto [to, r] : g[i]) w[r] = 1;
			}
			
			ll y = ask(w);
			
			if(y == x) l = m;
			else r = m;
		}
		
		rt = r - 1;
	}
	
	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);
		}
	};
	
	auto calc = [&](ll rt){
		bfs(rt);
		
		//~ cout<<rt<<endl;
		
		ll l = 0, r = n;
		while(l + 1 < r){
			ll m = (l + r) / 2;
			
			if(r - l > 60000) m = 60000;
			
			w.assign(M, 1);
			
			//~ 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 tour[r - 1];
	};
	
	s = calc(rt);
	
	t = calc(s);
	
	answer(s, t);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 3 ms 9800 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 2 ms 9816 KB Output is correct
5 Correct 3 ms 9816 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 3 ms 9816 KB Output is correct
8 Correct 2 ms 9816 KB Output is correct
9 Correct 3 ms 9816 KB Output is correct
10 Correct 2 ms 9768 KB Output is correct
11 Correct 3 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 9924 KB Output is correct
2 Correct 12 ms 11352 KB Output is correct
3 Correct 92 ms 24244 KB Output is correct
4 Correct 93 ms 24216 KB Output is correct
5 Correct 101 ms 23988 KB Output is correct
6 Correct 95 ms 24008 KB Output is correct
7 Correct 84 ms 24252 KB Output is correct
8 Correct 86 ms 24240 KB Output is correct
9 Correct 82 ms 24268 KB Output is correct
10 Correct 103 ms 24172 KB Output is correct
11 Correct 90 ms 24248 KB Output is correct
12 Correct 102 ms 24548 KB Output is correct
13 Correct 100 ms 24284 KB Output is correct
14 Correct 96 ms 24392 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11608 KB Output is correct
2 Correct 21 ms 13320 KB Output is correct
3 Correct 23 ms 14896 KB Output is correct
4 Correct 70 ms 24512 KB Output is correct
5 Correct 68 ms 24516 KB Output is correct
6 Correct 69 ms 25132 KB Output is correct
7 Correct 69 ms 25724 KB Output is correct
8 Correct 72 ms 24852 KB Output is correct
9 Correct 69 ms 24904 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9816 KB Output is correct
2 Correct 10 ms 11476 KB Output is correct
3 Correct 66 ms 21368 KB Output is correct
4 Correct 107 ms 24112 KB Output is correct
5 Correct 79 ms 24044 KB Output is correct
6 Correct 84 ms 24168 KB Output is correct
7 Correct 84 ms 24056 KB Output is correct
8 Correct 83 ms 24064 KB Output is correct
9 Correct 98 ms 24216 KB Output is correct
10 Correct 100 ms 24236 KB Output is correct
11 Correct 112 ms 24496 KB Output is correct
12 Correct 99 ms 24436 KB Output is correct
13 Correct 106 ms 24540 KB Output is correct
14 Correct 110 ms 24412 KB Output is correct
15 Correct 110 ms 24096 KB Output is correct
16 Correct 90 ms 24176 KB Output is correct
17 Correct 105 ms 24488 KB Output is correct
18 Correct 107 ms 24396 KB Output is correct
19 Correct 90 ms 24124 KB Output is correct
20 Correct 95 ms 24612 KB Output is correct
21 Correct 88 ms 25880 KB Output is correct
22 Correct 90 ms 24652 KB Output is correct
23 Correct 78 ms 24888 KB Output is correct
24 Correct 85 ms 25088 KB Output is correct
25 Correct 105 ms 25516 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11452 KB Output is correct
2 Correct 12 ms 11608 KB Output is correct
3 Correct 102 ms 25884 KB Output is correct
4 Correct 116 ms 26332 KB Output is correct
5 Correct 131 ms 28088 KB Output is correct
6 Correct 132 ms 28216 KB Output is correct
7 Correct 141 ms 28328 KB Output is correct
8 Correct 129 ms 28208 KB Output is correct
9 Correct 109 ms 22244 KB Output is correct
10 Correct 98 ms 23000 KB Output is correct
11 Correct 110 ms 24228 KB Output is correct
12 Correct 136 ms 26824 KB Output is correct
13 Correct 128 ms 27512 KB Output is correct
14 Correct 131 ms 28152 KB Output is correct
15 Correct 124 ms 28084 KB Output is correct
16 Correct 115 ms 24324 KB Output is correct
17 Correct 98 ms 25192 KB Output is correct
18 Correct 87 ms 25556 KB Output is correct
19 Correct 84 ms 25208 KB Output is correct
20 Correct 99 ms 25388 KB Output is correct
21 Correct 124 ms 27916 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11352 KB Output is correct
2 Correct 15 ms 11644 KB Output is correct
3 Partially correct 98 ms 25144 KB Output is partially correct
4 Partially correct 112 ms 26076 KB Output is partially correct
5 Partially correct 118 ms 26420 KB Output is partially correct
6 Correct 127 ms 28404 KB Output is correct
7 Correct 95 ms 25188 KB Output is correct
8 Partially correct 121 ms 25896 KB Output is partially correct
9 Partially correct 111 ms 26360 KB Output is partially correct
10 Partially correct 116 ms 28200 KB Output is partially correct
11 Partially correct 131 ms 28412 KB Output is partially correct
12 Partially correct 123 ms 28148 KB Output is partially correct
13 Correct 116 ms 24724 KB Output is correct
14 Correct 113 ms 22680 KB Output is correct
15 Correct 101 ms 24860 KB Output is correct
16 Correct 98 ms 23028 KB Output is correct
17 Correct 108 ms 24204 KB Output is correct
18 Correct 106 ms 22692 KB Output is correct
19 Partially correct 128 ms 26904 KB Output is partially correct
20 Partially correct 138 ms 27516 KB Output is partially correct
21 Partially correct 133 ms 28088 KB Output is partially correct
22 Correct 130 ms 28252 KB Output is correct
23 Partially correct 141 ms 28184 KB Output is partially correct
24 Partially correct 145 ms 28124 KB Output is partially correct
25 Partially correct 142 ms 28148 KB Output is partially correct
26 Partially correct 130 ms 28164 KB Output is partially correct
27 Partially correct 85 ms 25516 KB Output is partially correct
28 Partially correct 81 ms 24260 KB Output is partially correct
29 Partially correct 86 ms 25784 KB Output is partially correct
30 Partially correct 89 ms 25252 KB Output is partially correct
31 Partially correct 86 ms 25232 KB Output is partially correct
32 Partially correct 93 ms 25096 KB Output is partially correct
33 Correct 107 ms 25708 KB Output is correct
34 Partially correct 83 ms 24756 KB Output is partially correct
35 Partially correct 85 ms 25356 KB Output is partially correct
36 Partially correct 80 ms 25144 KB Output is partially correct
37 Partially correct 91 ms 25744 KB Output is partially correct
38 Partially correct 107 ms 25512 KB Output is partially correct
39 Partially correct 128 ms 27928 KB Output is partially correct
40 Partially correct 122 ms 28072 KB Output is partially correct
41 Correct 135 ms 27956 KB Output is correct
42 Partially correct 127 ms 27912 KB Output is partially correct