oj.uz

Submission #794108

# Submission time Handle Problem Language Result Execution time Memory
794108 2023-07-26T09:24:50 Z NothingXD Highway Tolls (IOI18_highway) C++17
5 / 100
 192 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 (h[i] == 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 1 ms 2640 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 1 ms 2640 KB Output is correct
6 Correct 1 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 2 ms 2640 KB Output is correct
11 Correct 2 ms 2640 KB Output is correct
12 Correct 1 ms 2640 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 8 ms 3280 KB Output is correct
3 Correct 104 ms 8876 KB Output is correct
4 Correct 73 ms 8992 KB Output is correct
5 Correct 132 ms 8884 KB Output is correct
6 Correct 71 ms 8892 KB Output is correct
7 Correct 74 ms 8804 KB Output is correct
8 Correct 64 ms 8884 KB Output is correct
9 Correct 112 ms 8756 KB Output is correct
10 Correct 103 ms 8920 KB Output is correct
11 Correct 93 ms 10368 KB Output is correct
12 Correct 123 ms 11340 KB Output is correct
13 Incorrect 118 ms 10512 KB Output is incorrect: {s, t} is wrong.
14 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4048 KB Output is correct
2 Incorrect 17 ms 5532 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2732 KB Output is correct
2 Correct 10 ms 3364 KB Output is correct
3 Incorrect 83 ms 7468 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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