oj.uz

Submission #794112

# Submission time Handle Problem Language Result Execution time Memory
794112 2023-07-26T09:26:08 Z NothingXD Highway Tolls (IOI18_highway) C++17
51 / 100
 188 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double ld;
typedef complex<ld> point;

void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

int n, m, h[maxn], par[maxn], edge[maxn][2], cnt;
vector<int> g[maxn];
vector<int> cand;
ll query1(int x){
	cnt++;
	if (cnt > 60) assert(0);
	//debug(x);
	vector<int> q(m, 0);
	for (int i = 0; i < n; i++){
		if (h[i] >= x) q[par[i]] = 1;
	}
	//for (int i = 0; i < m; i++) debug(i, q[i]);
	return ask(q);
}

ll query2(int x){
	cnt++;
	if (cnt > 60) assert(0);
	//debug(x);
	vector<int> q(m, 0);
	for (int i = 0; i <= x; i++){
		q[par[cand[i]]] = 1;
	}
	//debug()
	return ask(q);
}

void dfs(int v, int x = -1){
	par[v] = x;
	//debug(v, h[v], par[v]);
	for (auto i: g[v]){
		if (i == x) continue;
		int u = edge[i][0]^edge[i][1]^v;
		h[u] = h[v] + 1;
		dfs(u, i);
	}
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n = N;
	m = U.size();
	for (int i = 0; i < m; i++){
		edge[i][0] = U[i];
		edge[i][1] = V[i];
		g[U[i]].push_back(i);
		g[V[i]].push_back(i);
	}
	dfs(0);
	int mx = max_element(h, h+n) - h;
	ll dis = query1(n);
	//debug(dis);
	int l = 0, r = h[mx]+1;
	while(l + 1 < r){
		int mid = (l + r) >> 1;
		if (query1(mid) > dis) l = mid;
		else r = mid;
	}
	//debug(l);
	for (int i = 0; i < n; i++) if (h[i] == l) cand.push_back(i);


	//for (auto x: cand) debug(x);

	l = -1, r = cand.size() - 1;
	while(l + 1 < r){
		int mid = (l + r) >> 1;
		if (query2(mid) > dis) r = mid;
		else l = mid;
	}
	int r1 = cand[r];
	//debug(r1);
	h[r1] = 0;
	dfs(r1);

	//debug(l);
	
	cand.clear();
	for (int i = 0; i < n; i++) if (1ll * h[i] * A == dis) cand.push_back(i);

	l = -1, r = cand.size() - 1;
	while(l + 1 < r){
		int mid = (l + r) >> 1;
		if (query2(mid) > dis) r = mid;
		else l = mid;
	}
	int r2 = cand[r];
	//debug(r2);
	answer(r1, r2);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2732 KB Output is correct
2 Correct 10 ms 3372 KB Output is correct
3 Correct 77 ms 8872 KB Output is correct
4 Correct 83 ms 8872 KB Output is correct
5 Correct 92 ms 8868 KB Output is correct
6 Correct 82 ms 8772 KB Output is correct
7 Correct 110 ms 8888 KB Output is correct
8 Correct 110 ms 8908 KB Output is correct
9 Correct 125 ms 8872 KB Output is correct
10 Correct 98 ms 8872 KB Output is correct
11 Correct 96 ms 10364 KB Output is correct
12 Correct 96 ms 11336 KB Output is correct
13 Correct 101 ms 10508 KB Output is correct
14 Correct 84 ms 10552 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4048 KB Output is correct
2 Correct 18 ms 5560 KB Output is correct
3 Correct 21 ms 6980 KB Output is correct
4 Correct 104 ms 15692 KB Output is correct
5 Correct 82 ms 15692 KB Output is correct
6 Correct 88 ms 15688 KB Output is correct
7 Correct 57 ms 15692 KB Output is correct
8 Correct 77 ms 15688 KB Output is correct
9 Correct 63 ms 15680 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2732 KB Output is correct
2 Correct 13 ms 3232 KB Output is correct
3 Correct 72 ms 7460 KB Output is correct
4 Correct 88 ms 8816 KB Output is correct
5 Correct 66 ms 8812 KB Output is correct
6 Correct 110 ms 8872 KB Output is correct
7 Correct 115 ms 8808 KB Output is correct
8 Correct 89 ms 8880 KB Output is correct
9 Correct 91 ms 8884 KB Output is correct
10 Correct 103 ms 8884 KB Output is correct
11 Correct 111 ms 10200 KB Output is correct
12 Correct 115 ms 11212 KB Output is correct
13 Correct 125 ms 10624 KB Output is correct
14 Correct 105 ms 11144 KB Output is correct
15 Correct 88 ms 8852 KB Output is correct
16 Correct 92 ms 8808 KB Output is correct
17 Correct 87 ms 10792 KB Output is correct
18 Correct 110 ms 11052 KB Output is correct
19 Correct 91 ms 8808 KB Output is correct
20 Correct 81 ms 11728 KB Output is correct
21 Correct 112 ms 9612 KB Output is correct
22 Correct 102 ms 9520 KB Output is correct
23 Correct 79 ms 9524 KB Output is correct
24 Correct 106 ms 10192 KB Output is correct
25 Correct 107 ms 15020 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 188 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 174 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -