oj.uz

Submission #799389

# Submission time Handle Problem Language Result Execution time Memory
799389 2023-07-31T13:41:36 Z NothingXD Highway Tolls (IOI18_highway) C++17
18 / 100
 128 ms 26716 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 == 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;
	int x = 1, y = 3;
	while(l + 1 < r){
		vector<int> q(m, 0);
		int dis = r - l;
		int mid = l + dis * x / y;
		for (int i = 0; i <= mid; i++){
			for (auto x: g[i]){
				q[x] = 1;
			}
		}
		if (ask(q) == dis) l = mid;
		else r = mid;
	}
	for (int i = 0; i < r; i++){
		bad[i] = true;
	}
	int sz = n - r;
	//debug(r);
	bfs(r);
//	for (int i = 0; i < m; i++) debug(i, mark[i]);
	l = 0, r = sz;
	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 = sz, r = 0;
	for (int i = 0; i < sz; 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 3 ms 6688 KB Output is correct
2 Correct 4 ms 6736 KB Output is correct
3 Correct 4 ms 6680 KB Output is correct
4 Correct 3 ms 6736 KB Output is correct
5 Correct 3 ms 6684 KB Output is correct
6 Correct 3 ms 6736 KB Output is correct
7 Correct 3 ms 6688 KB Output is correct
8 Correct 3 ms 6736 KB Output is correct
9 Correct 3 ms 6736 KB Output is correct
10 Correct 4 ms 6684 KB Output is correct
11 Correct 4 ms 6680 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 12 ms 7468 KB Output is correct
3 Correct 108 ms 13252 KB Output is correct
4 Correct 114 ms 13260 KB Output is correct
5 Correct 111 ms 13260 KB Output is correct
6 Correct 86 ms 13332 KB Output is correct
7 Correct 99 ms 13268 KB Output is correct
8 Correct 97 ms 13268 KB Output is correct
9 Correct 87 ms 13296 KB Output is correct
10 Correct 100 ms 13384 KB Output is correct
11 Correct 128 ms 13128 KB Output is correct
12 Correct 116 ms 13108 KB Output is correct
13 Correct 94 ms 13120 KB Output is correct
14 Correct 82 ms 13112 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7480 KB Output is correct
2 Correct 24 ms 8112 KB Output is correct
3 Correct 30 ms 8868 KB Output is correct
4 Correct 77 ms 13120 KB Output is correct
5 Correct 65 ms 13112 KB Output is correct
6 Correct 81 ms 13112 KB Output is correct
7 Correct 66 ms 13024 KB Output is correct
8 Correct 64 ms 13112 KB Output is correct
9 Correct 64 ms 13108 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6744 KB Output is correct
2 Correct 11 ms 7400 KB Output is correct
3 Correct 77 ms 11836 KB Output is correct
4 Correct 82 ms 13256 KB Output is correct
5 Correct 80 ms 13260 KB Output is correct
6 Correct 80 ms 13272 KB Output is correct
7 Correct 77 ms 13260 KB Output is correct
8 Correct 94 ms 13260 KB Output is correct
9 Correct 121 ms 13256 KB Output is correct
10 Correct 123 ms 13372 KB Output is correct
11 Correct 86 ms 13128 KB Output is correct
12 Correct 94 ms 13128 KB Output is correct
13 Correct 104 ms 13112 KB Output is correct
14 Correct 83 ms 13120 KB Output is correct
15 Correct 86 ms 13268 KB Output is correct
16 Correct 90 ms 13356 KB Output is correct
17 Correct 82 ms 13124 KB Output is correct
18 Correct 87 ms 13120 KB Output is correct
19 Runtime error 79 ms 26716 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 7428 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 7504 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -