oj.uz

Submission #794096

# Submission time Handle Problem Language Result Execution time Memory
794096 2023-07-26T09:18:10 Z NothingXD Highway Tolls (IOI18_highway) C++17
11 / 100
 218 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];
vector<int> g[maxn];
vector<int> cand;
ll query1(int x){
	//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){
	//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 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 1 ms 2640 KB Output is correct
5 Correct 2 ms 2644 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 2 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 3 ms 2640 KB Output is correct
2 Correct 12 ms 3288 KB Output is correct
3 Correct 96 ms 8936 KB Output is correct
4 Correct 125 ms 8864 KB Output is correct
5 Incorrect 91 ms 8872 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4104 KB Output is correct
2 Correct 23 ms 5560 KB Output is correct
3 Correct 34 ms 7112 KB Output is correct
4 Correct 94 ms 15696 KB Output is correct
5 Correct 109 ms 15704 KB Output is correct
6 Correct 94 ms 15692 KB Output is correct
7 Correct 84 ms 15696 KB Output is correct
8 Correct 91 ms 15684 KB Output is correct
9 Correct 93 ms 15680 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 13 ms 3280 KB Output is correct
3 Correct 69 ms 7480 KB Output is correct
4 Correct 112 ms 8808 KB Output is correct
5 Correct 116 ms 8828 KB Output is correct
6 Correct 83 ms 8876 KB Output is correct
7 Correct 110 ms 8856 KB Output is correct
8 Correct 79 ms 8880 KB Output is correct
9 Correct 98 ms 8876 KB Output is correct
10 Incorrect 116 ms 8952 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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