oj.uz

Submission #1015462

# Submission time Handle Problem Language Result Execution time Memory
1015462 2024-07-06T11:15:36 Z mansur Highway Tolls (IOI18_highway) C++17
11 / 100
 121 ms 54896 KB 
#include "highway.h"
#include<bits/stdc++.h>

using namespace std;

#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()
#define s second
#define f first

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int N = 1e6;

vector<pii> g[N];
vector<int> s[N], h;

int n;

void bfs(int u) {
	queue<int> q;
	vector<int> d(n, -1);
	d[u] = 0;
	q.push(u);
	while (sz(q)) {
		int x = q.front();
		s[d[x]].push_back(x);
		q.pop();
		for (auto [to, id]: g[x]) {
			if (d[to] == -1) {
				d[to] = d[x] + 1;
				q.push(to);
			}
		}
	}
}

void find_pair(int n1, vector<int> u, vector<int> v, int a, int b) {
	n = n1;
	for (int i = 0; i < sz(u); i++) {
		g[u[i]].push_back({v[i], i});
		g[v[i]].push_back({u[i], i});
	}
	vector<int> w(sz(u));
	ll dt = ask(w);	
	int l = 0, r = sz(u) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) w[i] = 1;
		if (ask(w) == dt) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) w[i] = 0;
	}
	int x = u[l], y = v[l];
	bfs(y);
	l = 0, r = n;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = m; i <= n; i++) {
			for (int vt: s[i]) {
				for (auto [to, id]: g[vt]) {
					w[id] = 1;
				}
			}
		}
		if (ask(w) == dt) r = m - 1;
		else l = m + 1;
		for (int i = m; i <= n; i++) {
			for (int vt: s[i]) {
				for (auto [to, id]: g[vt]) {
					w[id] = 0;
				}
			}
		}
	}
	int z = r;
	l = 0, r = sz(s[z]) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) {
			for (auto [to, id]: g[s[z][i]]) {
				w[id] = 1;	
		   	}
		}  	
		if (ask(w) == dt) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) {
			for (auto [to, id]: g[s[z][i]]) {
				w[id] = 0;	
		   	}
		}
	}
	x = s[z][l];
	dt /= a;
	for (int i = 0; i <= n; i++) s[i].clear();
	bfs(x);
	h = s[dt];
	l = 0, r = sz(h) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) {
			for (auto [to, id]: g[h[i]]) w[id] = 1;
		}
		if (ask(w) == dt * 1ll * a) l = m + 1;
		else r = m - 1;
		for (int i = 0; i <= m; i++) {
			for (auto [to, id]: g[h[i]]) w[id] = 0;
		}
	}
	answer(x, h[l]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47192 KB Output is correct
2 Correct 9 ms 47192 KB Output is correct
3 Correct 8 ms 47192 KB Output is correct
4 Correct 8 ms 47192 KB Output is correct
5 Correct 8 ms 47276 KB Output is correct
6 Correct 9 ms 47192 KB Output is correct
7 Correct 8 ms 47192 KB Output is correct
8 Correct 7 ms 47192 KB Output is correct
9 Correct 10 ms 47404 KB Output is correct
10 Correct 8 ms 47192 KB Output is correct
11 Correct 8 ms 47192 KB Output is correct
12 Correct 8 ms 47356 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 47448 KB Output is correct
2 Correct 17 ms 47960 KB Output is correct
3 Correct 121 ms 53532 KB Output is correct
4 Correct 106 ms 53644 KB Output is correct
5 Correct 108 ms 53692 KB Output is correct
6 Correct 95 ms 53692 KB Output is correct
7 Incorrect 114 ms 53684 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 48168 KB Output is correct
2 Correct 23 ms 48984 KB Output is correct
3 Correct 38 ms 49688 KB Output is correct
4 Correct 83 ms 53848 KB Output is correct
5 Correct 85 ms 54000 KB Output is correct
6 Correct 72 ms 54640 KB Output is correct
7 Correct 81 ms 54896 KB Output is correct
8 Correct 74 ms 54184 KB Output is correct
9 Correct 100 ms 54368 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47448 KB Output is correct
2 Correct 17 ms 48072 KB Output is correct
3 Correct 89 ms 52020 KB Output is correct
4 Correct 102 ms 53436 KB Output is correct
5 Correct 96 ms 53520 KB Output is correct
6 Correct 100 ms 53392 KB Output is correct
7 Correct 93 ms 53356 KB Output is correct
8 Correct 93 ms 53264 KB Output is correct
9 Correct 100 ms 53392 KB Output is correct
10 Incorrect 113 ms 53712 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47960 KB Output is correct
2 Correct 20 ms 48164 KB Output is correct
3 Incorrect 105 ms 54236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 48008 KB Output is correct
2 Correct 19 ms 48052 KB Output is correct
3 Incorrect 117 ms 54040 KB Output isn't correct
4 Halted 0 ms 0 KB -