oj.uz

Submission #349623

# Submission time Handle Problem Language Result Execution time Memory
349623 2021-01-18T03:29:23 Z tengiz05 Highway Tolls (IOI18_highway) C++17
90 / 100
 434 ms 24240 KB 
#include "highway.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<ll,ll>
typedef long long ll;
const int _N = 90005;
vector<int> edges[_N];
vector<pii> edge[_N];
vector<pii> EDGES;
int n, m, a, b;
ll dist;
pii num(ll x){
	ll dif = x-dist;
	assert(dif%(b-a)==0);
	return {dist - dif/(b-a),dif/(b-a)};
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	n = N;
	m = U.size();
	a=A,b=B;
	for(int i=0;i<m;i++){
		edges[U[i]].pb(V[i]);
		edges[V[i]].pb(U[i]);
		edge[U[i]].pb({V[i],i});
		edge[V[i]].pb({U[i],i});
		EDGES.pb({U[i],V[i]});
	}
	vector<int> toask(m,0);
	ll TMP = ask(toask);
	dist = TMP;
	int l=0,r=m-1;
	while(l < r){
		int mid = (l+r)>>1;
		for(int i=0;i<=mid;i++)toask[i] = 1;
		for(int i=mid+1;i<m;i++)toask[i] = 0;
		ll tmp = ask(toask);
		if(tmp == dist)l = mid+1;
		else r = mid;
	}
	int root = EDGES[l].first;
	
	
	vector<int> should_be_B;
	vector<int> prohibited(m,0);
	{
		queue<pii> q;
		vector<int> Dist(n,2e9);Dist[root] = 0;
		q.push({root,root});
		while(!q.empty()){
			auto [u, p] = q.front();q.pop();
			for(auto [to, ind] : edge[u]){
				if(to == p)continue;
				if(Dist[to] <= Dist[u]+1){
					should_be_B.pb(ind);
					prohibited[ind] = 1;
				}else if(Dist[to] == 2e9){
					Dist[to] = Dist[u] + 1;
					q.push({to, u});
				}
			}
		}
	}
	
	//~ cout << EDGES[l].first << ';' << EDGES[l].second << '\n';
	//~ cout << l << '-' << r << '\n';
	queue<int> q;
	vector<bool> used(n,0);
	q.push(root);used[root] = true;
	vector<int> v;
	vector<pii> vse;
	while(!q.empty()){
		int u = q.front();q.pop();
		for(auto [to, ind] : edge[u]){
			if(used[to] || prohibited[ind])continue;
			used[to] = true;
			vse.pb({u, to});
			v.pb(ind);
			q.push(to);
		}
	}
	l=0,r=v.size()-1;
	while(l < r){
		int mid = (l+r)>>1;
		for(int i=0;i<=mid;i++)toask[v[i]] = 0;
		for(int i=mid+1;i<(int)v.size();i++)toask[v[i]] = 1;
		for(auto x : should_be_B)toask[x] = 1;
		auto [x, y] = num(ask(toask));
		if(y != 0)l = mid+1;
		else r = mid;
	}
	//~ cout << l << '-' << r << '\n';
	//~ cout << EDGES[v[l]].first << ' ' << EDGES[v[l]].second << '\n';
	//~ for(auto [x, y] : vse){
		//~ cout << x << ';' << y << '\n';
	//~ }
	prohibited.assign(m,0);
	should_be_B.clear();

	int s = vse[l].second;
	root = s;
	{
		queue<pii> q;
		vector<int> Dist(n,2e9);Dist[root] = 0;
		q.push({root,root});
		while(!q.empty()){
			auto [u, p] = q.front();q.pop();
			for(auto [to, ind] : edge[u]){
				if(to == p)continue;
				if(Dist[to] <= Dist[u]+1){
					should_be_B.pb(ind);
					prohibited[ind] = 1;
				}else if(Dist[to] == 2e9){
					Dist[to] = Dist[u] + 1;
					q.push({to, u});
				}
			}
		}
	}
	vse.clear();
	used.assign(n,0);
	q.push(root);used[root] = true;
	v.clear();
	while(!q.empty()){
		int u = q.front();q.pop();
		for(auto [to, ind] : edge[u]){
			if(used[to])continue;
			used[to] = true;
			vse.pb({u, to});
			v.pb(ind);
			q.push(to);
		}
	}
	l=0,r=v.size()-1;
	while(l < r){
		int mid = (l+r)>>1;
		for(int i=0;i<=mid;i++)toask[v[i]] = 0;
		for(int i=mid+1;i<(int)v.size();i++)toask[v[i]] = 1;
		for(auto x : should_be_B)toask[x] = 1;
		auto [x, y] = num(ask(toask));
		if(y != 0)l = mid+1;
		else r = mid;
	}
	int t = vse[l].second;
	//~ cout << s << ' ' << t << '\n';
	answer(s,t);
	
	return;
}


/*


7 6
1 2
3 4
0 2
0 3
3 4
2 6
2 5
2 1


5 4
1 2
4 2
0 1
0 2
0 3
0 4

3 2
100000 1000000000
0 1
1 2
1 0

*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4716 KB Output is correct
2 Correct 21 ms 6248 KB Output is correct
3 Correct 250 ms 19404 KB Output is correct
4 Correct 251 ms 19488 KB Output is correct
5 Correct 249 ms 19440 KB Output is correct
6 Correct 236 ms 19460 KB Output is correct
7 Correct 251 ms 19360 KB Output is correct
8 Correct 241 ms 19456 KB Output is correct
9 Correct 252 ms 19508 KB Output is correct
10 Correct 249 ms 19608 KB Output is correct
11 Correct 255 ms 19372 KB Output is correct
12 Correct 261 ms 19352 KB Output is correct
13 Correct 265 ms 19372 KB Output is correct
14 Correct 250 ms 19364 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6120 KB Output is correct
2 Correct 34 ms 7780 KB Output is correct
3 Correct 52 ms 8972 KB Output is correct
4 Correct 149 ms 18748 KB Output is correct
5 Correct 144 ms 18824 KB Output is correct
6 Correct 149 ms 18740 KB Output is correct
7 Correct 147 ms 18824 KB Output is correct
8 Correct 142 ms 18744 KB Output is correct
9 Correct 148 ms 18752 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4716 KB Output is correct
2 Correct 23 ms 6248 KB Output is correct
3 Correct 175 ms 16668 KB Output is correct
4 Correct 247 ms 19500 KB Output is correct
5 Correct 235 ms 19396 KB Output is correct
6 Correct 247 ms 19460 KB Output is correct
7 Correct 242 ms 19556 KB Output is correct
8 Correct 241 ms 19348 KB Output is correct
9 Correct 248 ms 19564 KB Output is correct
10 Correct 251 ms 19636 KB Output is correct
11 Correct 253 ms 19488 KB Output is correct
12 Correct 251 ms 19360 KB Output is correct
13 Correct 258 ms 19416 KB Output is correct
14 Correct 261 ms 19368 KB Output is correct
15 Correct 234 ms 19724 KB Output is correct
16 Correct 229 ms 19568 KB Output is correct
17 Correct 252 ms 19496 KB Output is correct
18 Correct 256 ms 19568 KB Output is correct
19 Correct 237 ms 19636 KB Output is correct
20 Correct 252 ms 19360 KB Output is correct
21 Correct 188 ms 19596 KB Output is correct
22 Correct 176 ms 19336 KB Output is correct
23 Correct 191 ms 19792 KB Output is correct
24 Correct 195 ms 19584 KB Output is correct
25 Correct 245 ms 19372 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6376 KB Output is correct
2 Correct 29 ms 6376 KB Output is correct
3 Correct 278 ms 20432 KB Output is correct
4 Correct 304 ms 21536 KB Output is correct
5 Correct 369 ms 24028 KB Output is correct
6 Correct 365 ms 23916 KB Output is correct
7 Correct 355 ms 23928 KB Output is correct
8 Correct 378 ms 23896 KB Output is correct
9 Correct 235 ms 18788 KB Output is correct
10 Correct 245 ms 20472 KB Output is correct
11 Correct 267 ms 21348 KB Output is correct
12 Correct 348 ms 23220 KB Output is correct
13 Correct 339 ms 23684 KB Output is correct
14 Correct 360 ms 24180 KB Output is correct
15 Correct 373 ms 24024 KB Output is correct
16 Correct 289 ms 21456 KB Output is correct
17 Correct 196 ms 19504 KB Output is correct
18 Correct 208 ms 19804 KB Output is correct
19 Correct 203 ms 19592 KB Output is correct
20 Correct 205 ms 19764 KB Output is correct
21 Correct 365 ms 23648 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6376 KB Output is correct
2 Correct 27 ms 6376 KB Output is correct
3 Partially correct 284 ms 20484 KB Output is partially correct
4 Correct 299 ms 20844 KB Output is correct
5 Partially correct 302 ms 21460 KB Output is partially correct
6 Partially correct 383 ms 24044 KB Output is partially correct
7 Partially correct 279 ms 20404 KB Output is partially correct
8 Partially correct 300 ms 20792 KB Output is partially correct
9 Partially correct 312 ms 21616 KB Output is partially correct
10 Correct 368 ms 23888 KB Output is correct
11 Partially correct 350 ms 23900 KB Output is partially correct
12 Partially correct 367 ms 24040 KB Output is partially correct
13 Correct 266 ms 21484 KB Output is correct
14 Correct 249 ms 20480 KB Output is correct
15 Correct 238 ms 21328 KB Output is correct
16 Correct 263 ms 20616 KB Output is correct
17 Correct 264 ms 21340 KB Output is correct
18 Correct 235 ms 20588 KB Output is correct
19 Correct 334 ms 23500 KB Output is correct
20 Correct 359 ms 23732 KB Output is correct
21 Partially correct 370 ms 24112 KB Output is partially correct
22 Partially correct 418 ms 24056 KB Output is partially correct
23 Partially correct 383 ms 24240 KB Output is partially correct
24 Partially correct 378 ms 24120 KB Output is partially correct
25 Partially correct 358 ms 24020 KB Output is partially correct
26 Correct 371 ms 24176 KB Output is correct
27 Partially correct 201 ms 19780 KB Output is partially correct
28 Partially correct 249 ms 19536 KB Output is partially correct
29 Partially correct 202 ms 20032 KB Output is partially correct
30 Partially correct 253 ms 19680 KB Output is partially correct
31 Correct 227 ms 19664 KB Output is correct
32 Partially correct 228 ms 19464 KB Output is partially correct
33 Correct 255 ms 20016 KB Output is correct
34 Correct 199 ms 19872 KB Output is correct
35 Partially correct 205 ms 19664 KB Output is partially correct
36 Correct 236 ms 19396 KB Output is correct
37 Partially correct 224 ms 19952 KB Output is partially correct
38 Partially correct 220 ms 20064 KB Output is partially correct
39 Partially correct 364 ms 23652 KB Output is partially correct
40 Partially correct 434 ms 23564 KB Output is partially correct
41 Correct 433 ms 23584 KB Output is correct
42 Partially correct 351 ms 23680 KB Output is partially correct