oj.uz

Submission #1015493

# Submission time Handle Problem Language Result Execution time Memory
1015493 2024-07-06T11:44:55 Z mansur Highway Tolls (IOI18_highway) C++17
0 / 100
 42 ms 95740 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);
	for (int i = 1; i <= n; i++) {
		for (int vt: s[i]) {
			for (auto [to, id]: g[vt]) {
				w[id] = 1;
			}
		}
	}
	ll diff = ask(w) - dt;
	diff /= b - a;
	for (int i = 1; i <= n; i++) {
		for (int vt: s[i]) {
			for (auto [to, id]: g[vt]) {
				w[id] = 0;
			}
		}
	}
	int z = diff;
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 47192 KB Output is correct
2 Runtime error 42 ms 95740 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 47448 KB Output is correct
2 Incorrect 19 ms 47984 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 47960 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 20 ms 48008 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -