Submission #1058353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1058353	2024-08-14T09:31:55 Z	ReLice	Highway Tolls (IOI18_highway)	C++17	90 / 100	152 ms	28652 KB

highway

#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);
		}
	};
	
	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:96:7: warning: variable 'calc' set but not used [-Wunused-but-set-variable]
   96 |  auto calc = [&](ll n){
      |       ^~~~
highway.cpp:144:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |  s = tour[ans];
      |              ^

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	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	3 ms	9816 KB	Output is correct
9	Correct	2 ms	9816 KB	Output is correct
10	Correct	2 ms	9816 KB	Output is correct
11	Correct	3 ms	9816 KB	Output is correct
12	Correct	3 ms	9816 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	9816 KB	Output is correct
2	Correct	9 ms	11448 KB	Output is correct
3	Correct	106 ms	24044 KB	Output is correct
4	Correct	81 ms	24276 KB	Output is correct
5	Correct	94 ms	24048 KB	Output is correct
6	Correct	104 ms	24024 KB	Output is correct
7	Correct	76 ms	24044 KB	Output is correct
8	Correct	83 ms	24248 KB	Output is correct
9	Correct	72 ms	24232 KB	Output is correct
10	Correct	96 ms	24256 KB	Output is correct
11	Correct	81 ms	24280 KB	Output is correct
12	Correct	102 ms	24536 KB	Output is correct
13	Correct	77 ms	24508 KB	Output is correct
14	Correct	92 ms	24340 KB	Output is correct

Subtask #3

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	11620 KB	Output is correct
2	Correct	16 ms	13376 KB	Output is correct
3	Correct	24 ms	14924 KB	Output is correct
4	Correct	70 ms	24588 KB	Output is correct
5	Correct	65 ms	24532 KB	Output is correct
6	Correct	72 ms	25656 KB	Output is correct
7	Correct	70 ms	25588 KB	Output is correct
8	Correct	63 ms	24816 KB	Output is correct
9	Correct	77 ms	24860 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	12 ms	11352 KB	Output is correct
3	Correct	61 ms	21404 KB	Output is correct
4	Correct	77 ms	24112 KB	Output is correct
5	Correct	64 ms	24040 KB	Output is correct
6	Correct	76 ms	24172 KB	Output is correct
7	Correct	71 ms	24136 KB	Output is correct
8	Correct	72 ms	23972 KB	Output is correct
9	Correct	87 ms	24176 KB	Output is correct
10	Correct	77 ms	24020 KB	Output is correct
11	Correct	95 ms	24500 KB	Output is correct
12	Correct	92 ms	24444 KB	Output is correct
13	Correct	102 ms	24516 KB	Output is correct
14	Correct	100 ms	24476 KB	Output is correct
15	Correct	67 ms	24084 KB	Output is correct
16	Correct	81 ms	24128 KB	Output is correct
17	Correct	109 ms	24552 KB	Output is correct
18	Correct	85 ms	24548 KB	Output is correct
19	Correct	76 ms	24168 KB	Output is correct
20	Correct	78 ms	24628 KB	Output is correct
21	Correct	74 ms	24832 KB	Output is correct
22	Correct	78 ms	24656 KB	Output is correct
23	Correct	73 ms	24532 KB	Output is correct
24	Correct	79 ms	24796 KB	Output is correct
25	Correct	92 ms	26308 KB	Output is correct

Subtask #5

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	11608 KB	Output is correct
2	Correct	10 ms	11604 KB	Output is correct
3	Correct	94 ms	25420 KB	Output is correct
4	Correct	98 ms	26320 KB	Output is correct
5	Correct	116 ms	28300 KB	Output is correct
6	Correct	115 ms	28152 KB	Output is correct
7	Correct	119 ms	28144 KB	Output is correct
8	Correct	136 ms	28212 KB	Output is correct
9	Correct	97 ms	21964 KB	Output is correct
10	Correct	97 ms	22812 KB	Output is correct
11	Correct	133 ms	24236 KB	Output is correct
12	Correct	117 ms	26784 KB	Output is correct
13	Correct	119 ms	27492 KB	Output is correct
14	Correct	112 ms	28152 KB	Output is correct
15	Correct	110 ms	28092 KB	Output is correct
16	Correct	98 ms	24292 KB	Output is correct
17	Correct	88 ms	24612 KB	Output is correct
18	Correct	75 ms	24632 KB	Output is correct
19	Correct	77 ms	24392 KB	Output is correct
20	Correct	90 ms	24632 KB	Output is correct
21	Correct	104 ms	28036 KB	Output is correct

Subtask #6

21.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	11352 KB	Output is correct
2	Correct	11 ms	11460 KB	Output is correct
3	Correct	86 ms	25180 KB	Output is correct
4	Correct	99 ms	25852 KB	Output is correct
5	Correct	102 ms	26428 KB	Output is correct
6	Correct	106 ms	28140 KB	Output is correct
7	Correct	108 ms	25240 KB	Output is correct
8	Correct	94 ms	25860 KB	Output is correct
9	Correct	99 ms	26456 KB	Output is correct
10	Correct	102 ms	28172 KB	Output is correct
11	Correct	116 ms	28580 KB	Output is correct
12	Correct	111 ms	28140 KB	Output is correct
13	Correct	110 ms	24256 KB	Output is correct
14	Correct	105 ms	22684 KB	Output is correct
15	Correct	111 ms	24444 KB	Output is correct
16	Correct	115 ms	23120 KB	Output is correct
17	Correct	112 ms	24208 KB	Output is correct
18	Correct	99 ms	22696 KB	Output is correct
19	Correct	114 ms	26892 KB	Output is correct
20	Correct	113 ms	27528 KB	Output is correct
21	Correct	125 ms	28192 KB	Output is correct
22	Correct	120 ms	28180 KB	Output is correct
23	Correct	130 ms	28652 KB	Output is correct
24	Correct	111 ms	28104 KB	Output is correct
25	Correct	152 ms	28144 KB	Output is correct
26	Correct	117 ms	28112 KB	Output is correct
27	Correct	84 ms	24456 KB	Output is correct
28	Correct	80 ms	24260 KB	Output is correct
29	Correct	77 ms	24868 KB	Output is correct
30	Correct	87 ms	24424 KB	Output is correct
31	Partially correct	95 ms	24744 KB	Output is partially correct
32	Correct	84 ms	24276 KB	Output is correct
33	Correct	88 ms	25048 KB	Output is correct
34	Correct	83 ms	24760 KB	Output is correct
35	Correct	79 ms	24632 KB	Output is correct
36	Correct	84 ms	24236 KB	Output is correct
37	Correct	95 ms	25256 KB	Output is correct
38	Partially correct	96 ms	24656 KB	Output is partially correct
39	Correct	101 ms	27900 KB	Output is correct
40	Correct	136 ms	27844 KB	Output is correct
41	Partially correct	134 ms	27980 KB	Output is partially correct
42	Correct	136 ms	28060 KB	Output is correct