oj.uz

Submission #799372

# Submission time Handle Problem Language Result Execution time Memory
799372 2023-07-31T13:28:42 Z NothingXD Highway Tolls (IOI18_highway) C++17
90 / 100
 190 ms 14820 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 = 2e5 + 10;

int n, m, h[maxn], par[maxn], st[maxn], ver[maxn], tme, edge[maxn][2], cnt;
vector<int> g[maxn];
bool mark[maxn];

void bfs(int V){
	memset(h, -1, sizeof h);
	memset(par, -1, sizeof par);
	memset(mark, true, sizeof mark);
	queue<int> q;
	q.push(V);
	tme = 0;
	h[V] = 0;
	st[V] = 0;
	par[V] = -1;
	ver[0] = V;
	while(!q.empty()){
		int v = q.front();	
		//debug(v, h[v], par[v], st[v], ver[st[v]]);
		q.pop();
		for (auto x: g[v]){
			int u = edge[x][0]^edge[x][1]^v;
			if (h[u] == -1){
				h[u] = h[v] + 1;
				par[u] = x;
				st[u] = ++tme;
				ver[tme] = u;
				mark[x] = false;
				q.push(u);
			}
		}
	}
	assert(tme == n-1);
}

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);
	}

	vector<int> q(m, 0);
	ll dis = ask(q);
	int l = -1, r = n-1;
	while(l + 1 < r){
		vector<int> q(m, 0);
		int mid = (l + r) >> 1;
		for (int i = 0; i <= mid; i++){
			for (auto x: g[i]){
				q[x] = 1;
			}
		}
		if (ask(q) == dis) l = mid;
		else r = mid;
	}
	//debug(r);
	bfs(r);
//	for (int i = 0; i < m; i++) debug(i, mark[i]);
	l = 0, r = n;
	while(l + 1 < r){
		vector<int> q(m, 0);
		int mid = (l + r) >> 1;
	//	debug(mid);
		for (int i = 0; i < m; i++) q[i] = mark[i];
		for (int i = mid; i < n; i++){
			q[par[ver[i]]] = 1;
		}
	//	for (int i = 0; i < m; i++) debug(i, q[i]);
		if (ask(q) == dis) r = mid;
		else l = mid;
	}
	int S = ver[l];
	bfs(S);
	//debug(S);
//	for (int i = 0; i < m; i++) debug(i, mark[i]);

	l = n, r = 0;
	for (int i = 0; i < n; i++){
	//	debug(i, ver[i], h[ver[i]] * A, dis);
		if (1ll * h[ver[i]] * A == dis){
			l = min(l, i);
			r = max(r, i);
		}
	}
	r++;
	while(l + 1 < r){
		vector<int> q(m, 0);
		int mid = (l + r) >> 1;
	//	debug(mid);
		for (int i = 0; i < m; i++) q[i] = mark[i];
		for (int i = mid; i < n; i++){
			q[par[ver[i]]] = 1;
		}
		//for (int i = 0; i < m; i++) debug(i, q[i]);
		if (ask(q) == dis) r = mid;
		else l = mid;
	}
//	debug(ver[l]);
	answer(S, ver[l]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6736 KB Output is correct
2 Correct 3 ms 6736 KB Output is correct
3 Correct 4 ms 6736 KB Output is correct
4 Correct 3 ms 6756 KB Output is correct
5 Correct 3 ms 6680 KB Output is correct
6 Correct 3 ms 6736 KB Output is correct
7 Correct 3 ms 6680 KB Output is correct
8 Correct 4 ms 6736 KB Output is correct
9 Correct 3 ms 6784 KB Output is correct
10 Correct 3 ms 6684 KB Output is correct
11 Correct 3 ms 6736 KB Output is correct
12 Correct 3 ms 6736 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6736 KB Output is correct
2 Correct 28 ms 7364 KB Output is correct
3 Correct 142 ms 13256 KB Output is correct
4 Correct 158 ms 13268 KB Output is correct
5 Correct 107 ms 13268 KB Output is correct
6 Correct 100 ms 13248 KB Output is correct
7 Correct 99 ms 13256 KB Output is correct
8 Correct 128 ms 13268 KB Output is correct
9 Correct 111 ms 13256 KB Output is correct
10 Correct 104 ms 13260 KB Output is correct
11 Correct 87 ms 13272 KB Output is correct
12 Correct 103 ms 13104 KB Output is correct
13 Correct 127 ms 13108 KB Output is correct
14 Correct 108 ms 13108 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7388 KB Output is correct
2 Correct 22 ms 8172 KB Output is correct
3 Correct 24 ms 8868 KB Output is correct
4 Correct 86 ms 13128 KB Output is correct
5 Correct 89 ms 13120 KB Output is correct
6 Correct 85 ms 13060 KB Output is correct
7 Correct 65 ms 13176 KB Output is correct
8 Correct 60 ms 13336 KB Output is correct
9 Correct 96 ms 13104 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6732 KB Output is correct
2 Correct 12 ms 7416 KB Output is correct
3 Correct 67 ms 11836 KB Output is correct
4 Correct 117 ms 13256 KB Output is correct
5 Correct 107 ms 13256 KB Output is correct
6 Correct 89 ms 13248 KB Output is correct
7 Correct 115 ms 13256 KB Output is correct
8 Correct 167 ms 13244 KB Output is correct
9 Correct 125 ms 13244 KB Output is correct
10 Correct 138 ms 13268 KB Output is correct
11 Correct 133 ms 13116 KB Output is correct
12 Correct 124 ms 13144 KB Output is correct
13 Correct 132 ms 13108 KB Output is correct
14 Correct 92 ms 13108 KB Output is correct
15 Correct 104 ms 13268 KB Output is correct
16 Correct 94 ms 13252 KB Output is correct
17 Correct 107 ms 13112 KB Output is correct
18 Correct 112 ms 13108 KB Output is correct
19 Correct 101 ms 13260 KB Output is correct
20 Correct 109 ms 13116 KB Output is correct
21 Correct 122 ms 13584 KB Output is correct
22 Correct 95 ms 13484 KB Output is correct
23 Correct 103 ms 13700 KB Output is correct
24 Correct 95 ms 13604 KB Output is correct
25 Correct 120 ms 13184 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7468 KB Output is correct
2 Correct 16 ms 7504 KB Output is correct
3 Correct 142 ms 13628 KB Output is correct
4 Correct 142 ms 13996 KB Output is correct
5 Correct 180 ms 14764 KB Output is correct
6 Correct 165 ms 14740 KB Output is correct
7 Correct 157 ms 14748 KB Output is correct
8 Correct 143 ms 14732 KB Output is correct
9 Correct 120 ms 12852 KB Output is correct
10 Correct 106 ms 13084 KB Output is correct
11 Correct 121 ms 13172 KB Output is correct
12 Correct 157 ms 14288 KB Output is correct
13 Correct 190 ms 14492 KB Output is correct
14 Correct 151 ms 14616 KB Output is correct
15 Correct 126 ms 14596 KB Output is correct
16 Correct 114 ms 13584 KB Output is correct
17 Correct 90 ms 13592 KB Output is correct
18 Correct 109 ms 13644 KB Output is correct
19 Correct 128 ms 13608 KB Output is correct
20 Correct 90 ms 13696 KB Output is correct
21 Correct 132 ms 14604 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7480 KB Output is correct
2 Correct 11 ms 7564 KB Output is correct
3 Correct 84 ms 13672 KB Output is correct
4 Correct 154 ms 13812 KB Output is correct
5 Correct 153 ms 13992 KB Output is correct
6 Correct 179 ms 14808 KB Output is correct
7 Correct 125 ms 13688 KB Output is correct
8 Correct 131 ms 14004 KB Output is correct
9 Correct 144 ms 13992 KB Output is correct
10 Correct 169 ms 14820 KB Output is correct
11 Correct 136 ms 14748 KB Output is correct
12 Correct 158 ms 14756 KB Output is correct
13 Correct 130 ms 13140 KB Output is correct
14 Correct 86 ms 13088 KB Output is correct
15 Correct 156 ms 13156 KB Output is correct
16 Correct 96 ms 13108 KB Output is correct
17 Correct 111 ms 13084 KB Output is correct
18 Correct 131 ms 13172 KB Output is correct
19 Correct 130 ms 14316 KB Output is correct
20 Correct 138 ms 14400 KB Output is correct
21 Correct 153 ms 14612 KB Output is correct
22 Correct 138 ms 14588 KB Output is correct
23 Correct 162 ms 14616 KB Output is correct
24 Correct 143 ms 14616 KB Output is correct
25 Correct 179 ms 14672 KB Output is correct
26 Correct 153 ms 14636 KB Output is correct
27 Correct 111 ms 13680 KB Output is correct
28 Partially correct 109 ms 13576 KB Output is partially correct
29 Partially correct 127 ms 13756 KB Output is partially correct
30 Partially correct 121 ms 13660 KB Output is partially correct
31 Partially correct 96 ms 13624 KB Output is partially correct
32 Partially correct 111 ms 13540 KB Output is partially correct
33 Correct 129 ms 13908 KB Output is correct
34 Correct 119 ms 13748 KB Output is correct
35 Partially correct 100 ms 13632 KB Output is partially correct
36 Correct 108 ms 13544 KB Output is correct
37 Correct 132 ms 13712 KB Output is correct
38 Correct 101 ms 13732 KB Output is correct
39 Correct 116 ms 14600 KB Output is correct
40 Correct 149 ms 14596 KB Output is correct
41 Correct 183 ms 14620 KB Output is correct
42 Correct 127 ms 14612 KB Output is correct