oj.uz

Submission #295466

# Submission time Handle Problem Language Result Execution time Memory
295466 2020-09-09T17:00:00 Z amoo_safar Highway Tolls (IOI18_highway) C++17
100 / 100
 339 ms 24628 KB 
#include "highway.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int N = 2e5 + 10;

vector<pii> G[N];
vector<int> H[N];
int E[N], dep[N], rem[N];
int T, fnt[N];

void DFS(int u, int p = -1, int d = 0){
	dep[u] = d;
	T ++;
	for(auto adj : H[u])
		if(adj != p)
			DFS(adj, u, d + 1);
	T ++;
	fnt[u] = T;
}

void find_pair(int _n, vector<int> U, vector<int> V, int A, int B){
	int n = _n;
	int m = U.size();
	//assert(m == n - 1);
	for(int i = 0; i < m; i++){
		G[U[i]].pb({V[i], i});
		G[V[i]].pb({U[i], i});
	}
	vector<int> W(m, 0);
	ll dis = ask(W);

	int src = -1;

	cerr << "*&^%$ " << dis << '\n';
	vector<int> I2(n, 0);
	iota(all(I2), 0);
	mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
	shuffle(all(I2), rng);

	{
		int L = 0, R = n;

		while(L + 1 < R){
			int mid = (L + R) >> 1;
			for(int i = 0; i < mid; i++) rem[I2[i]] = 1;
			for(int i = 0; i < m; i++) W[i] = (rem[U[i]] || rem[V[i]]);
			//cerr << "^ " << mid << ' ';
			//for(auto x : W) cerr << x;
			//cerr << '\n';
			if(ask(W) > dis) R = mid;
			else L = mid;

			for(int i = 0; i < mid; i++) rem[I2[i]] = 0;
		}
		src = I2[L];
		for(int i = 0; i < L; i++) rem[I2[i]] = true;
	}
	//src = 0;
	cerr << "@ " << src << '\n';


	queue<int> Q;
	vector<int> D(n, n);
	D[src] = 0; Q.push(src);
	int fr;
	while(!Q.empty()){
		fr = Q.front(); Q.pop();
		for(auto ed : G[fr]){
			int adj = ed.F;
			if(rem[adj]) continue;
			if(D[adj] > D[fr] + 1){
				D[adj] = D[fr] + 1;
				H[fr].pb(adj);
				H[adj].pb(fr);
				//cerr << "E : " << fr << ' ' << adj << '\n';
				Q.push(adj);
			}
		}
	}



	DFS(src);
	vector<int> I;
	for(int i = 0; i < n; i++) if(D[i] == n) rem[i] = 1;

	for(int i = 0; i < n; i++) if(!rem[i]) I.pb(i);

	sort(all(I), [&](int i, int j){
		return dep[i] > dep[j];
	});
	
	//cerr << "() " ;
	//for(auto x : I) cerr << x << ' ';
	//cerr << '\n';
	int st = -1, fn = -1;

	int L = 0, R = I.size();

	while(L + 1 < R){
		int mid = (L + R) >> 1;
		//for(int i = 0; i < m; i++) W[i] = 0;
		for(int i = 0; i < mid; i++) rem[I[i]] = 1;
		for(int i = 0; i < m; i++) W[i] = (rem[U[i]] || rem[V[i]]);

		if(ask(W) > dis) R = mid;
		else L = mid;

		for(int i = 0; i < mid; i++) rem[I[i]] = 0;
	}
	st = I[L];
	for(int i = 0; i < L; i++) rem[I[i]] = 1;

	cerr << "!! " << st << '\n';
	if(1ll * A * D[st] == dis){
		answer(src, st);
		return ;
	}
	
	I.clear();
	for(int i = 0; i < n; i++) if(!rem[i]) I.pb(i);

	DFS(st);
	sort(all(I), [&](int i, int j){
		return dep[i] > dep[j];
	});

	//cerr << "! " << st << ' ' << L << '\n';
	//cerr << "&&& ";
	//for(auto x : I) cerr << x;
	//cerr << '\n';
	assert(I.size() >= 2);
	//reverse(I.begin(), I.end() - 1);

	L = 0, R = I.size();

	while(L + 1 < R){
		int mid = (L + R) >> 1;
		//for(int i = 0; i < m; i++) W[i] = 0;
		for(int i = 0; i < mid; i++) rem[I[i]] = 1;
		for(int i = 0; i < m; i++) W[i] = (rem[U[i]] || rem[V[i]]);
		//cerr << "^ " << mid << ' ';
		//for(auto x : W) cerr << x;
		//cerr << '\n';
		if(ask(W) > dis) R = mid;
		else L = mid;

		for(int i = 0; i < mid; i++) rem[I[i]] = 0;
		//for(int i = 0; i < n; i++) cerr << rem[i];
		//cerr << '\n';
	}
	fn = I[L];
	cerr << "!! " << fn << '\n';
	assert(1ll * A * (D[fn] + D[st]) == dis);
	answer(st, fn);
	
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9856 KB Output is correct
2 Correct 24 ms 10752 KB Output is correct
3 Correct 219 ms 19708 KB Output is correct
4 Correct 216 ms 18804 KB Output is correct
5 Correct 215 ms 19652 KB Output is correct
6 Correct 205 ms 18300 KB Output is correct
7 Correct 199 ms 18788 KB Output is correct
8 Correct 187 ms 18416 KB Output is correct
9 Correct 160 ms 16848 KB Output is correct
10 Correct 225 ms 20376 KB Output is correct
11 Correct 196 ms 19220 KB Output is correct
12 Correct 236 ms 21492 KB Output is correct
13 Correct 238 ms 21032 KB Output is correct
14 Correct 205 ms 18860 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10368 KB Output is correct
2 Correct 40 ms 13040 KB Output is correct
3 Correct 48 ms 11864 KB Output is correct
4 Correct 146 ms 19256 KB Output is correct
5 Correct 125 ms 15460 KB Output is correct
6 Correct 163 ms 23912 KB Output is correct
7 Correct 122 ms 15456 KB Output is correct
8 Correct 164 ms 22808 KB Output is correct
9 Correct 126 ms 16280 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9856 KB Output is correct
2 Correct 36 ms 11128 KB Output is correct
3 Correct 119 ms 15444 KB Output is correct
4 Correct 189 ms 18728 KB Output is correct
5 Correct 186 ms 19392 KB Output is correct
6 Correct 141 ms 16804 KB Output is correct
7 Correct 141 ms 16128 KB Output is correct
8 Correct 181 ms 18812 KB Output is correct
9 Correct 224 ms 20376 KB Output is correct
10 Correct 192 ms 18568 KB Output is correct
11 Correct 226 ms 19452 KB Output is correct
12 Correct 231 ms 21520 KB Output is correct
13 Correct 248 ms 21024 KB Output is correct
14 Correct 179 ms 17828 KB Output is correct
15 Correct 191 ms 20080 KB Output is correct
16 Correct 146 ms 16312 KB Output is correct
17 Correct 245 ms 20896 KB Output is correct
18 Correct 211 ms 19780 KB Output is correct
19 Correct 167 ms 17652 KB Output is correct
20 Correct 151 ms 16520 KB Output is correct
21 Correct 188 ms 20676 KB Output is correct
22 Correct 153 ms 21220 KB Output is correct
23 Correct 183 ms 20996 KB Output is correct
24 Correct 196 ms 21312 KB Output is correct
25 Correct 245 ms 24628 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 10744 KB Output is correct
2 Correct 48 ms 11128 KB Output is correct
3 Correct 238 ms 20072 KB Output is correct
4 Correct 248 ms 20840 KB Output is correct
5 Correct 268 ms 21056 KB Output is correct
6 Correct 268 ms 21112 KB Output is correct
7 Correct 333 ms 21560 KB Output is correct
8 Correct 292 ms 20444 KB Output is correct
9 Correct 205 ms 16776 KB Output is correct
10 Correct 205 ms 16836 KB Output is correct
11 Correct 225 ms 17836 KB Output is correct
12 Correct 262 ms 19544 KB Output is correct
13 Correct 275 ms 20708 KB Output is correct
14 Correct 289 ms 21116 KB Output is correct
15 Correct 297 ms 21296 KB Output is correct
16 Correct 232 ms 18088 KB Output is correct
17 Correct 212 ms 21100 KB Output is correct
18 Correct 243 ms 19348 KB Output is correct
19 Correct 205 ms 18820 KB Output is correct
20 Correct 211 ms 20744 KB Output is correct
21 Correct 308 ms 21964 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10980 KB Output is correct
2 Correct 30 ms 10872 KB Output is correct
3 Correct 247 ms 20392 KB Output is correct
4 Correct 212 ms 19644 KB Output is correct
5 Correct 262 ms 20508 KB Output is correct
6 Correct 273 ms 21412 KB Output is correct
7 Correct 241 ms 19960 KB Output is correct
8 Correct 229 ms 20308 KB Output is correct
9 Correct 234 ms 20492 KB Output is correct
10 Correct 289 ms 21696 KB Output is correct
11 Correct 313 ms 21640 KB Output is correct
12 Correct 337 ms 20392 KB Output is correct
13 Correct 267 ms 17116 KB Output is correct
14 Correct 262 ms 17028 KB Output is correct
15 Correct 204 ms 17068 KB Output is correct
16 Correct 194 ms 16520 KB Output is correct
17 Correct 234 ms 18264 KB Output is correct
18 Correct 257 ms 17288 KB Output is correct
19 Correct 257 ms 19224 KB Output is correct
20 Correct 339 ms 20768 KB Output is correct
21 Correct 309 ms 21404 KB Output is correct
22 Correct 322 ms 21208 KB Output is correct
23 Correct 293 ms 21068 KB Output is correct
24 Correct 288 ms 21460 KB Output is correct
25 Correct 311 ms 20700 KB Output is correct
26 Correct 288 ms 21252 KB Output is correct
27 Correct 234 ms 19356 KB Output is correct
28 Correct 192 ms 19956 KB Output is correct
29 Correct 195 ms 20024 KB Output is correct
30 Correct 176 ms 20940 KB Output is correct
31 Correct 200 ms 20680 KB Output is correct
32 Correct 245 ms 20212 KB Output is correct
33 Correct 181 ms 19048 KB Output is correct
34 Correct 201 ms 18320 KB Output is correct
35 Correct 171 ms 20512 KB Output is correct
36 Correct 191 ms 20160 KB Output is correct
37 Correct 193 ms 19180 KB Output is correct
38 Correct 184 ms 18908 KB Output is correct
39 Correct 256 ms 19484 KB Output is correct
40 Correct 287 ms 20956 KB Output is correct
41 Correct 309 ms 21896 KB Output is correct
42 Correct 296 ms 21960 KB Output is correct