oj.uz

Submission #762224

# Submission time Handle Problem Language Result Execution time Memory
762224 2023-06-21T05:40:38 Z minhcool Highway Tolls (IOI18_highway) C++17
90 / 100
 218 ms 19372 KB 
//#define local
#ifndef local
#include "highway.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;

const ll N = 3e5 + 5;

const ll oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

ll rnd(ll l, ll r){
	ll temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

// ask(vector<ll>)

vector<ii> Adj[N];

ll mini;

ll n, m;

vector<ii> v1, v2;

bool vis[N];

bool ck = 0;

vector<int> ok;

int dist;

/*
void dfs(ll u, ll d){
	vis[u] = 1;
	if(!ck) v1.pb({u, d});
	else v2.pb({u, d});
//	if(d == dist) ok.pb(u);
	for(auto it : Adj[u]){
		if(it.se < (mini - 1)) continue;
		if(vis[it.fi]) continue;
		dfs(it.fi, d + 1);
	}
}*/

bool cmp(ii a, ii b){
	return a.se > b.se;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	n = N, m = U.size();
	for(ll i = 0; i < m; i++){
		Adj[U[i]].pb({V[i], i});
		Adj[V[i]].pb({U[i], i});
	}
	// first step: find the optimal ans by toggle all 0s
	ll opt;
	vector<int> temp;
	for(ll i = 0; i < m; i++) temp.pb(0);
	opt = ask(temp);
	// phase 1: let us set (1->i) to B in order to find a bridge + split graph llo two parts
	ll le = 0, ri = m - 1;
	while(le < ri){
		ll mid = (le + ri) >> 1;
		temp.clear();
		for(ll i = 0; i <= mid; i++) temp.pb(1);
		for(ll i = mid + 1; i < m; i++) temp.pb(0);
		ll get = ask(temp);
		if(get == opt) le = mid + 1;
		else ri = mid;
	}
	mini = le + 1;
	// phase 2: find S/T
	ck = 0;
	//dfs(U[le], 0);
	queue<int> q;
	vis[U[le]] = 1;
	q.push(U[le]);
	vector<int> distt(n + 1);
	while(!q.empty()){
		int u = q.front();
		q.pop();
	//	if(distt[u] == dist) ok.pb(u);
		v1.pb({u, distt[u]});
		for(auto it : Adj[u]){
			int v = it.fi;
			if(it.se < (mini - 1)) continue;
			if(!vis[v]){
				vis[v] = 1;
				distt[v] = distt[u] + 1;
				q.push(v);
			}
		}
	}
	//ck = 1;
	//dfs(V[le], 0);
	sort(v1.begin(), v1.end(), cmp);
	//sort(v2.begin(), v2.end(), cmp);
	ll le2 = 0, ri2 = v1.size() - 1;
	while(le2 < ri2){
		ll mid = (le2 + ri2) >> 1;
		temp.resize(m);
		for(ll i = 0; i < le; i++) temp[i] = 1;
		temp[le] = 0;
		for(ll i = le + 1; i < m; i++) temp[i] = 0;
		for(ll i = 0; i <= mid; i++){
			ll u = v1[i].fi;
			for(auto it : Adj[u]){
				if(it.se < mini) continue;
				temp[it.se] = 1;
			}
		}
		ll get = ask(temp);
		if(get == opt) le2 = mid + 1;
		else ri2 = mid;
	}
	/*
	ll le3 = 0, ri3 = v2.size() - 1;
	while(le3 < ri3){
		ll mid = (le3 + ri3) >> 1;
		temp.resize(m);
		for(ll i = 0; i < le; i++) temp[i] = 1;
		temp[le] = 0;
		for(ll i = le + 1; i < m; i++) temp[i] = 0;
		for(ll i = 0; i <= mid; i++){
			ll u = v2[i].fi;
			for(auto it : Adj[u]){
				if(it.se < mini) continue;
				temp[it.se] = 1;
			}
		}
		ll get = ask(temp);
		if(get == opt) le3 = mid + 1;
		else ri3 = mid;
	}*/
	int S = v1[(int)le2].fi;
	dist = opt / A;
//	cout << S << " " << opt << " " << A << " " << dist << "\n";
	ok.clear();
	mini = 0;
	for(int i = 0; i < n; i++) vis[i] = 0;
	for(int i = 0; i <= n; i++) distt[i] = 0;
	vis[S] = 1;
	q.push(S);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		if(distt[u] == dist) ok.pb(u);
		for(auto it : Adj[u]){
			int v = it.fi;
			if(!vis[v]){
				vis[v] = 1;
				distt[v] = distt[u] + 1;
				q.push(v);
			}
		}
	}
///	dfs(S, 0);
//	for(auto it : ok) cout << it << " ";
//	cout << "\n";
	assert(ok.size());
	int le3 = 0, ri3 = ok.size() - 1;
	while(le3 < ri3){
		int mid = (le3 + ri3) >> 1;
		temp.resize(m);
		for(int i = 0; i < m; i++) temp[i] = 0;
		for(int i = 0; i <= mid; i++){
			int u = ok[i];
			for(auto it : Adj[u]) temp[it.se] = 1;
		}
		ll get = ask(temp);
		if(get == opt) le3 = mid + 1;
		else ri3 = mid; 
	}
	int T = ok[le3];
	answer(S, T);
	//answer((int)v1[(int)le2].fi, (int)v2[(int)le3].fi);
}

#ifdef local
void process(){

}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll t;
	cin >> t;
	while(t--) process();
}
#endif

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7376 KB Output is correct
2 Correct 14 ms 8400 KB Output is correct
3 Correct 98 ms 16328 KB Output is correct
4 Correct 92 ms 16316 KB Output is correct
5 Correct 108 ms 16320 KB Output is correct
6 Correct 107 ms 15352 KB Output is correct
7 Correct 95 ms 15276 KB Output is correct
8 Correct 113 ms 16388 KB Output is correct
9 Correct 116 ms 15296 KB Output is correct
10 Correct 115 ms 15364 KB Output is correct
11 Correct 76 ms 14656 KB Output is correct
12 Correct 121 ms 16392 KB Output is correct
13 Correct 124 ms 16352 KB Output is correct
14 Correct 107 ms 16356 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8456 KB Output is correct
2 Correct 29 ms 9292 KB Output is correct
3 Correct 23 ms 9560 KB Output is correct
4 Correct 97 ms 14800 KB Output is correct
5 Correct 114 ms 14784 KB Output is correct
6 Correct 92 ms 15920 KB Output is correct
7 Correct 105 ms 13908 KB Output is correct
8 Correct 108 ms 14904 KB Output is correct
9 Correct 106 ms 14460 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7376 KB Output is correct
2 Correct 17 ms 8344 KB Output is correct
3 Correct 90 ms 14904 KB Output is correct
4 Correct 102 ms 16288 KB Output is correct
5 Correct 88 ms 14308 KB Output is correct
6 Correct 69 ms 14188 KB Output is correct
7 Correct 109 ms 15348 KB Output is correct
8 Correct 117 ms 14428 KB Output is correct
9 Correct 105 ms 16308 KB Output is correct
10 Correct 135 ms 15312 KB Output is correct
11 Correct 121 ms 16348 KB Output is correct
12 Correct 113 ms 16424 KB Output is correct
13 Correct 93 ms 15360 KB Output is correct
14 Correct 123 ms 14948 KB Output is correct
15 Correct 69 ms 14316 KB Output is correct
16 Correct 69 ms 14248 KB Output is correct
17 Correct 101 ms 16356 KB Output is correct
18 Correct 129 ms 16404 KB Output is correct
19 Correct 64 ms 14308 KB Output is correct
20 Correct 72 ms 14352 KB Output is correct
21 Correct 107 ms 16256 KB Output is correct
22 Correct 75 ms 15412 KB Output is correct
23 Correct 111 ms 16072 KB Output is correct
24 Correct 95 ms 16812 KB Output is correct
25 Correct 126 ms 16340 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8592 KB Output is correct
2 Correct 20 ms 8648 KB Output is correct
3 Correct 130 ms 17120 KB Output is correct
4 Correct 190 ms 17804 KB Output is correct
5 Correct 213 ms 19216 KB Output is correct
6 Correct 174 ms 19268 KB Output is correct
7 Correct 181 ms 19268 KB Output is correct
8 Correct 175 ms 19304 KB Output is correct
9 Correct 87 ms 15144 KB Output is correct
10 Correct 147 ms 16900 KB Output is correct
11 Correct 124 ms 17684 KB Output is correct
12 Correct 186 ms 19184 KB Output is correct
13 Correct 206 ms 19176 KB Output is correct
14 Correct 166 ms 19332 KB Output is correct
15 Correct 178 ms 19272 KB Output is correct
16 Correct 159 ms 17920 KB Output is correct
17 Correct 91 ms 16072 KB Output is correct
18 Correct 106 ms 15508 KB Output is correct
19 Correct 122 ms 16696 KB Output is correct
20 Correct 129 ms 15860 KB Output is correct
21 Correct 204 ms 19296 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 8528 KB Output is correct
2 Correct 19 ms 8656 KB Output is correct
3 Correct 144 ms 17116 KB Output is correct
4 Correct 206 ms 17420 KB Output is correct
5 Correct 186 ms 17796 KB Output is correct
6 Correct 148 ms 19252 KB Output is correct
7 Correct 129 ms 17136 KB Output is correct
8 Correct 167 ms 17480 KB Output is correct
9 Correct 163 ms 17856 KB Output is correct
10 Correct 191 ms 19240 KB Output is correct
11 Correct 175 ms 19260 KB Output is correct
12 Correct 187 ms 19312 KB Output is correct
13 Correct 169 ms 16392 KB Output is correct
14 Correct 95 ms 16296 KB Output is correct
15 Correct 151 ms 17876 KB Output is correct
16 Correct 157 ms 16940 KB Output is correct
17 Correct 138 ms 17768 KB Output is correct
18 Correct 160 ms 16992 KB Output is correct
19 Correct 162 ms 19136 KB Output is correct
20 Correct 208 ms 19292 KB Output is correct
21 Correct 218 ms 19276 KB Output is correct
22 Correct 187 ms 19292 KB Output is correct
23 Correct 172 ms 19264 KB Output is correct
24 Correct 196 ms 19280 KB Output is correct
25 Correct 217 ms 19228 KB Output is correct
26 Correct 203 ms 19304 KB Output is correct
27 Correct 90 ms 15932 KB Output is correct
28 Partially correct 99 ms 16612 KB Output is partially correct
29 Partially correct 147 ms 17220 KB Output is partially correct
30 Partially correct 96 ms 16780 KB Output is partially correct
31 Correct 109 ms 16660 KB Output is correct
32 Correct 131 ms 16608 KB Output is correct
33 Partially correct 127 ms 17236 KB Output is partially correct
34 Correct 136 ms 16276 KB Output is correct
35 Correct 109 ms 16272 KB Output is correct
36 Partially correct 121 ms 16536 KB Output is partially correct
37 Correct 147 ms 17112 KB Output is correct
38 Partially correct 140 ms 16760 KB Output is partially correct
39 Correct 191 ms 19340 KB Output is correct
40 Correct 180 ms 19348 KB Output is correct
41 Correct 155 ms 19368 KB Output is correct
42 Correct 199 ms 19372 KB Output is correct