oj.uz

Submission #1058144

# Submission time Handle Problem Language Result Execution time Memory
1058144 2024-08-14T08:41:50 Z ReLice Highway Tolls (IOI18_highway) C++17
36 / 100
 132 ms 28504 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(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 - 1)];
	
	answer(s, t);
}

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 9664 KB Output is correct
10 Correct 2 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 9816 KB Output is correct
2 Correct 9 ms 11352 KB Output is correct
3 Correct 93 ms 24244 KB Output is correct
4 Correct 91 ms 24268 KB Output is correct
5 Correct 96 ms 24056 KB Output is correct
6 Correct 91 ms 24040 KB Output is correct
7 Correct 83 ms 24280 KB Output is correct
8 Correct 83 ms 24260 KB Output is correct
9 Correct 77 ms 24276 KB Output is correct
10 Correct 85 ms 24212 KB Output is correct
11 Correct 86 ms 24464 KB Output is correct
12 Correct 109 ms 24552 KB Output is correct
13 Correct 78 ms 24300 KB Output is correct
14 Correct 93 ms 24304 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11536 KB Output is correct
2 Correct 16 ms 13228 KB Output is correct
3 Correct 22 ms 14844 KB Output is correct
4 Correct 67 ms 24612 KB Output is correct
5 Correct 65 ms 24620 KB Output is correct
6 Correct 67 ms 25340 KB Output is correct
7 Correct 65 ms 25620 KB Output is correct
8 Correct 74 ms 25384 KB Output is correct
9 Correct 64 ms 25068 KB Output is correct

Subtask #4
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 66 ms 21388 KB Output is correct
4 Correct 94 ms 24168 KB Output is correct
5 Correct 83 ms 24124 KB Output is correct
6 Correct 73 ms 24172 KB Output is correct
7 Correct 71 ms 24128 KB Output is correct
8 Correct 73 ms 24136 KB Output is correct
9 Correct 95 ms 24020 KB Output is correct
10 Correct 77 ms 24036 KB Output is correct
11 Correct 105 ms 24540 KB Output is correct
12 Correct 91 ms 24408 KB Output is correct
13 Correct 97 ms 24824 KB Output is correct
14 Correct 92 ms 24500 KB Output is correct
15 Correct 73 ms 24032 KB Output is correct
16 Incorrect 96 ms 24156 KB Output is incorrect: {s, t} is wrong.
17 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11352 KB Output is correct
2 Correct 10 ms 11608 KB Output is correct
3 Correct 112 ms 25416 KB Output is correct
4 Correct 94 ms 26560 KB Output is correct
5 Correct 115 ms 28096 KB Output is correct
6 Correct 115 ms 28148 KB Output is correct
7 Correct 125 ms 28128 KB Output is correct
8 Correct 122 ms 28404 KB Output is correct
9 Correct 95 ms 21952 KB Output is correct
10 Correct 99 ms 22812 KB Output is correct
11 Correct 111 ms 24276 KB Output is correct
12 Correct 126 ms 26780 KB Output is correct
13 Correct 110 ms 27476 KB Output is correct
14 Correct 117 ms 28152 KB Output is correct
15 Correct 132 ms 28160 KB Output is correct
16 Correct 100 ms 24288 KB Output is correct
17 Correct 79 ms 24580 KB Output is correct
18 Correct 79 ms 24640 KB Output is correct
19 Correct 90 ms 24388 KB Output is correct
20 Correct 79 ms 24592 KB Output is correct
21 Correct 125 ms 28040 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11352 KB Output is correct
2 Correct 12 ms 11464 KB Output is correct
3 Correct 88 ms 25152 KB Output is correct
4 Correct 116 ms 25856 KB Output is correct
5 Partially correct 108 ms 26432 KB Output is partially correct
6 Correct 128 ms 28068 KB Output is correct
7 Correct 93 ms 25184 KB Output is correct
8 Correct 94 ms 25876 KB Output is correct
9 Correct 93 ms 26344 KB Output is correct
10 Correct 111 ms 28160 KB Output is correct
11 Correct 119 ms 28124 KB Output is correct
12 Correct 119 ms 28504 KB Output is correct
13 Correct 107 ms 24444 KB Output is correct
14 Correct 95 ms 22676 KB Output is correct
15 Incorrect 94 ms 24256 KB Output is incorrect: {s, t} is wrong.
16 Halted 0 ms 0 KB -