oj.uz

Submission #1058146

# Submission time Handle Problem Language Result Execution time Memory
1058146 2024-08-14T08:42:19 Z ReLice Highway Tolls (IOI18_highway) C++17
90 / 100
 147 ms 28480 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);
		}
	};
	
	vll path;
	auto calc = [&](ll N){
		ll l = 0, r = N;
		while(l + 1 < r){
			ll m = (l + r) / 2;
			
			if(n == N && 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 k = calc(n);
	s = tour[k];
	
	{
		ll x = s;
		while(x != rt){
			path.pb(pr[x]);
			x = p[x];
		}
	}
	
	t = tour[calc(k)];
	
	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 9816 KB Output is correct
3 Correct 2 ms 9764 KB Output is correct
4 Correct 2 ms 9816 KB Output is correct
5 Correct 3 ms 9816 KB Output is correct
6 Correct 3 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 3 ms 9816 KB Output is correct
10 Correct 3 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 9888 KB Output is correct
2 Correct 10 ms 11488 KB Output is correct
3 Correct 96 ms 24224 KB Output is correct
4 Correct 92 ms 24484 KB Output is correct
5 Correct 86 ms 24008 KB Output is correct
6 Correct 81 ms 24088 KB Output is correct
7 Correct 89 ms 24284 KB Output is correct
8 Correct 99 ms 24276 KB Output is correct
9 Correct 72 ms 24124 KB Output is correct
10 Correct 81 ms 24280 KB Output is correct
11 Correct 78 ms 24240 KB Output is correct
12 Correct 87 ms 24600 KB Output is correct
13 Correct 80 ms 24400 KB Output is correct
14 Correct 95 ms 24284 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 13252 KB Output is correct
3 Correct 23 ms 14880 KB Output is correct
4 Correct 73 ms 25016 KB Output is correct
5 Correct 71 ms 24608 KB Output is correct
6 Correct 72 ms 25220 KB Output is correct
7 Correct 66 ms 25568 KB Output is correct
8 Correct 75 ms 24824 KB Output is correct
9 Correct 66 ms 24900 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 9 ms 11352 KB Output is correct
3 Correct 70 ms 21416 KB Output is correct
4 Correct 83 ms 24128 KB Output is correct
5 Correct 85 ms 24088 KB Output is correct
6 Correct 88 ms 24176 KB Output is correct
7 Correct 74 ms 24132 KB Output is correct
8 Correct 75 ms 24116 KB Output is correct
9 Correct 82 ms 24120 KB Output is correct
10 Correct 81 ms 24264 KB Output is correct
11 Correct 95 ms 24488 KB Output is correct
12 Correct 96 ms 24416 KB Output is correct
13 Correct 95 ms 24548 KB Output is correct
14 Correct 88 ms 24492 KB Output is correct
15 Correct 85 ms 24036 KB Output is correct
16 Correct 77 ms 24136 KB Output is correct
17 Correct 113 ms 24476 KB Output is correct
18 Correct 93 ms 24404 KB Output is correct
19 Correct 76 ms 24092 KB Output is correct
20 Correct 78 ms 24664 KB Output is correct
21 Correct 75 ms 24668 KB Output is correct
22 Correct 76 ms 24660 KB Output is correct
23 Correct 74 ms 24544 KB Output is correct
24 Correct 80 ms 24540 KB Output is correct
25 Correct 98 ms 26224 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 11344 KB Output is correct
2 Correct 11 ms 11608 KB Output is correct
3 Correct 94 ms 25412 KB Output is correct
4 Correct 94 ms 26328 KB Output is correct
5 Correct 111 ms 28096 KB Output is correct
6 Correct 119 ms 28308 KB Output is correct
7 Correct 115 ms 28148 KB Output is correct
8 Correct 116 ms 28208 KB Output is correct
9 Correct 105 ms 21972 KB Output is correct
10 Correct 107 ms 22812 KB Output is correct
11 Correct 104 ms 24232 KB Output is correct
12 Correct 113 ms 26764 KB Output is correct
13 Correct 116 ms 27472 KB Output is correct
14 Correct 111 ms 28152 KB Output is correct
15 Correct 113 ms 28480 KB Output is correct
16 Correct 94 ms 24296 KB Output is correct
17 Correct 78 ms 24508 KB Output is correct
18 Correct 83 ms 24752 KB Output is correct
19 Correct 96 ms 24376 KB Output is correct
20 Correct 93 ms 24560 KB Output is correct
21 Correct 111 ms 28032 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11352 KB Output is correct
2 Correct 11 ms 11608 KB Output is correct
3 Correct 85 ms 25236 KB Output is correct
4 Correct 93 ms 25864 KB Output is correct
5 Correct 97 ms 26424 KB Output is correct
6 Correct 133 ms 28452 KB Output is correct
7 Correct 102 ms 25112 KB Output is correct
8 Correct 113 ms 25876 KB Output is correct
9 Correct 94 ms 26332 KB Output is correct
10 Correct 107 ms 28164 KB Output is correct
11 Correct 147 ms 28344 KB Output is correct
12 Correct 135 ms 28144 KB Output is correct
13 Correct 114 ms 24272 KB Output is correct
14 Correct 108 ms 22688 KB Output is correct
15 Correct 124 ms 24232 KB Output is correct
16 Correct 103 ms 22804 KB Output is correct
17 Correct 110 ms 24196 KB Output is correct
18 Correct 97 ms 22700 KB Output is correct
19 Correct 120 ms 27296 KB Output is correct
20 Correct 111 ms 27516 KB Output is correct
21 Correct 115 ms 28084 KB Output is correct
22 Correct 120 ms 28176 KB Output is correct
23 Correct 109 ms 28172 KB Output is correct
24 Correct 120 ms 28176 KB Output is correct
25 Correct 118 ms 28136 KB Output is correct
26 Correct 124 ms 28112 KB Output is correct
27 Correct 74 ms 24468 KB Output is correct
28 Correct 92 ms 24272 KB Output is correct
29 Correct 91 ms 25152 KB Output is correct
30 Correct 84 ms 24416 KB Output is correct
31 Partially correct 83 ms 24368 KB Output is partially correct
32 Correct 104 ms 24288 KB Output is correct
33 Correct 82 ms 25048 KB Output is correct
34 Correct 88 ms 24744 KB Output is correct
35 Correct 77 ms 24648 KB Output is correct
36 Correct 88 ms 24292 KB Output is correct
37 Correct 83 ms 24780 KB Output is correct
38 Partially correct 95 ms 24848 KB Output is partially correct
39 Correct 123 ms 28072 KB Output is correct
40 Correct 110 ms 27812 KB Output is correct
41 Partially correct 136 ms 28048 KB Output is partially correct
42 Correct 124 ms 27960 KB Output is correct