oj.uz

Submission #794103

# Submission time Handle Problem Language Result Execution time Memory
794103 2023-07-26T09:22:25 Z NothingXD Highway Tolls (IOI18_highway) C++17
11 / 100
 204 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);
	ll dis = query1(n);
	//debug(dis);
	int l = 0, r = n;
	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);

	l = 0, r = n;
	while(l + 1 < r){
		int mid = (l + r) >> 1;
		if (query1(mid) > dis) l = mid;
		else r = mid;
	}

	//debug(l);
	
	cand.clear();
	for (int i = 0; i < n; i++) if (h[i] == l) 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 1 ms 2640 KB Output is correct
2 Correct 1 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 1 ms 2640 KB Output is correct
6 Correct 2 ms 2640 KB Output is correct
7 Correct 2 ms 2640 KB Output is correct
8 Correct 2 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 2 ms 2640 KB Output is correct
12 Correct 2 ms 2640 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2728 KB Output is correct
2 Correct 11 ms 3280 KB Output is correct
3 Correct 101 ms 8868 KB Output is correct
4 Correct 85 ms 8872 KB Output is correct
5 Runtime error 127 ms 17836 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4112 KB Output is correct
2 Correct 14 ms 5576 KB Output is correct
3 Correct 22 ms 7092 KB Output is correct
4 Correct 66 ms 15696 KB Output is correct
5 Correct 67 ms 15700 KB Output is correct
6 Correct 88 ms 15692 KB Output is correct
7 Correct 67 ms 15704 KB Output is correct
8 Correct 97 ms 15708 KB Output is correct
9 Correct 104 ms 15708 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 9 ms 3280 KB Output is correct
3 Correct 73 ms 7464 KB Output is correct
4 Correct 101 ms 8812 KB Output is correct
5 Correct 121 ms 8852 KB Output is correct
6 Correct 88 ms 8876 KB Output is correct
7 Correct 107 ms 8812 KB Output is correct
8 Correct 85 ms 8872 KB Output is correct
9 Correct 93 ms 8888 KB Output is correct
10 Runtime error 97 ms 17740 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 204 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 173 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -