oj.uz

Submission #799423

# Submission time Handle Problem Language Result Execution time Memory
799423 2023-07-31T14:05:51 Z NothingXD Highway Tolls (IOI18_highway) C++17
100 / 100
 190 ms 14744 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];
bool bad[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 (!bad[u] && 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 == sz-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);
	//debug(dis);
	int l = -1, r = n-1;
	int x = 1, y = 2;
	while(l + 1 < r){
		vector<int> q(m, 0);
		int diff = r - l;
		int mid = l + diff * x / y;
		mid = max(mid, l+1);
		mid = min(mid, r-1);
		//debug(l, r, mid);
		for (int i = 0; i <= mid; i++){
			for (auto x: g[i]){
				q[x] = 1;
			}
		}
		//for (int i = 0; i < m; i++) debug(i, q[i]);
		if (ask(q) == dis) l = mid;
		else r = mid;
	}
	for (int i = 0; i < r; i++){
		bad[i] = true;
	}
//	debug(r);
	bfs(r);
//	for (int i = 0; i < m; i++) debug(i, mark[i]);
	l = 0, r = tme+1;
	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 < tme+1; 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 = tme+1, r = 0;
	for (int i = 0; i < tme+1; 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 < tme+1; 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 6784 KB Output is correct
2 Correct 3 ms 6736 KB Output is correct
3 Correct 3 ms 6736 KB Output is correct
4 Correct 4 ms 6736 KB Output is correct
5 Correct 4 ms 6736 KB Output is correct
6 Correct 4 ms 6736 KB Output is correct
7 Correct 3 ms 6684 KB Output is correct
8 Correct 3 ms 6736 KB Output is correct
9 Correct 3 ms 6736 KB Output is correct
10 Correct 3 ms 6736 KB Output is correct
11 Correct 3 ms 6736 KB Output is correct
12 Correct 3 ms 6680 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6736 KB Output is correct
2 Correct 11 ms 7388 KB Output is correct
3 Correct 96 ms 13268 KB Output is correct
4 Correct 102 ms 13268 KB Output is correct
5 Correct 126 ms 13268 KB Output is correct
6 Correct 103 ms 13252 KB Output is correct
7 Correct 114 ms 13260 KB Output is correct
8 Correct 126 ms 13268 KB Output is correct
9 Correct 112 ms 13268 KB Output is correct
10 Correct 105 ms 13264 KB Output is correct
11 Correct 85 ms 13128 KB Output is correct
12 Correct 87 ms 13124 KB Output is correct
13 Correct 81 ms 13124 KB Output is correct
14 Correct 84 ms 13128 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7376 KB Output is correct
2 Correct 16 ms 8100 KB Output is correct
3 Correct 29 ms 8660 KB Output is correct
4 Correct 78 ms 12888 KB Output is correct
5 Correct 87 ms 12888 KB Output is correct
6 Correct 50 ms 12980 KB Output is correct
7 Correct 79 ms 12540 KB Output is correct
8 Correct 95 ms 12944 KB Output is correct
9 Correct 81 ms 12664 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6736 KB Output is correct
2 Correct 11 ms 7376 KB Output is correct
3 Correct 79 ms 11696 KB Output is correct
4 Correct 86 ms 12956 KB Output is correct
5 Correct 118 ms 13232 KB Output is correct
6 Correct 98 ms 12840 KB Output is correct
7 Correct 97 ms 13020 KB Output is correct
8 Correct 92 ms 12944 KB Output is correct
9 Correct 113 ms 13172 KB Output is correct
10 Correct 114 ms 13232 KB Output is correct
11 Correct 78 ms 12852 KB Output is correct
12 Correct 97 ms 13056 KB Output is correct
13 Correct 96 ms 13028 KB Output is correct
14 Correct 117 ms 13012 KB Output is correct
15 Correct 86 ms 13164 KB Output is correct
16 Correct 81 ms 12928 KB Output is correct
17 Correct 105 ms 13004 KB Output is correct
18 Correct 115 ms 12876 KB Output is correct
19 Correct 95 ms 12708 KB Output is correct
20 Correct 109 ms 12808 KB Output is correct
21 Correct 108 ms 13316 KB Output is correct
22 Correct 137 ms 13168 KB Output is correct
23 Correct 79 ms 13660 KB Output is correct
24 Correct 90 ms 13612 KB Output is correct
25 Correct 120 ms 13196 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 7504 KB Output is correct
2 Correct 18 ms 7528 KB Output is correct
3 Correct 147 ms 13596 KB Output is correct
4 Correct 132 ms 13880 KB Output is correct
5 Correct 170 ms 14688 KB Output is correct
6 Correct 171 ms 14628 KB Output is correct
7 Correct 156 ms 14688 KB Output is correct
8 Correct 163 ms 14696 KB Output is correct
9 Correct 117 ms 12736 KB Output is correct
10 Correct 149 ms 12960 KB Output is correct
11 Correct 133 ms 12860 KB Output is correct
12 Correct 144 ms 14180 KB Output is correct
13 Correct 161 ms 14488 KB Output is correct
14 Correct 160 ms 14528 KB Output is correct
15 Correct 152 ms 14552 KB Output is correct
16 Correct 134 ms 13536 KB Output is correct
17 Correct 99 ms 13544 KB Output is correct
18 Correct 82 ms 13528 KB Output is correct
19 Correct 123 ms 13592 KB Output is correct
20 Correct 117 ms 13508 KB Output is correct
21 Correct 117 ms 14604 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7504 KB Output is correct
2 Correct 17 ms 7496 KB Output is correct
3 Correct 124 ms 13552 KB Output is correct
4 Correct 121 ms 13756 KB Output is correct
5 Correct 137 ms 13844 KB Output is correct
6 Correct 128 ms 14728 KB Output is correct
7 Correct 99 ms 13580 KB Output is correct
8 Correct 121 ms 13816 KB Output is correct
9 Correct 146 ms 14004 KB Output is correct
10 Correct 133 ms 14732 KB Output is correct
11 Correct 190 ms 14664 KB Output is correct
12 Correct 124 ms 14744 KB Output is correct
13 Correct 106 ms 12888 KB Output is correct
14 Correct 129 ms 13080 KB Output is correct
15 Correct 147 ms 12972 KB Output is correct
16 Correct 135 ms 13080 KB Output is correct
17 Correct 99 ms 12836 KB Output is correct
18 Correct 114 ms 13084 KB Output is correct
19 Correct 127 ms 14176 KB Output is correct
20 Correct 156 ms 14320 KB Output is correct
21 Correct 186 ms 14492 KB Output is correct
22 Correct 147 ms 14460 KB Output is correct
23 Correct 145 ms 14592 KB Output is correct
24 Correct 162 ms 14560 KB Output is correct
25 Correct 153 ms 14284 KB Output is correct
26 Correct 179 ms 14620 KB Output is correct
27 Correct 123 ms 13484 KB Output is correct
28 Correct 111 ms 13428 KB Output is correct
29 Correct 89 ms 13556 KB Output is correct
30 Correct 86 ms 13384 KB Output is correct
31 Correct 92 ms 13504 KB Output is correct
32 Correct 134 ms 13340 KB Output is correct
33 Correct 109 ms 13608 KB Output is correct
34 Correct 112 ms 13592 KB Output is correct
35 Correct 129 ms 13628 KB Output is correct
36 Correct 98 ms 13396 KB Output is correct
37 Correct 102 ms 13520 KB Output is correct
38 Correct 135 ms 13472 KB Output is correct
39 Correct 143 ms 14600 KB Output is correct
40 Correct 131 ms 14592 KB Output is correct
41 Correct 161 ms 14704 KB Output is correct
42 Correct 127 ms 14616 KB Output is correct