Submission #1017470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017470		mansur	Highway Tolls (IOI18_highway)	C++17	51 / 100	126 ms	37128 KiB

highway

#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];

int n, m1;

void find_pair(int n1, vector<int> u, vector<int> v, int a, int b) {
	n = n1, m1 = sz(u);
	for (int i = 0; i < m1; 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];
	queue<int> q;
	vector<int> d(n, -1), tp(n, -1), is(m1);
	vector<pii> s[2][n];
	d[x] = 0, d[y] = 0;
	tp[x] = 0, tp[y] = 1;
	is[l] = -1;
	s[0][0] = {{x, l}};
	s[1][0] = {{y, l}};
	q.push(x);
	q.push(y);
	while (sz(q)) {
		int a = q.front();
		q.pop();
		for (auto [to, id]: g[a]) {
			if (d[to] == -1) {
				tp[to] = tp[a];
            	d[to] = d[a] + 1;
            	q.push(to);
				s[tp[to]][d[to]].push_back({to, id});
            	is[id] = 1;
            }
		}
	}
	for (int i = 0; i < m1; i++) {
		if (!is[i]) {
			w[i] = 1;
			continue;
		}
	}
	for (int i = 0; i < m1; i++) {
		if (is[i] == 1 && tp[u[i]]) w[i] = 1;		
	}
	ll td = ask(w);
	int dt1 = (td - dt) / (b - a);
	for (int i = 0; i < m1; i++) {
		if (is[i] == 1 && tp[u[i]]) w[i] = 0;		
	}
	int dt0 = dt / a - dt1 - 1;
	l = 0, r = sz(s[0][dt0]) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) {
			w[s[0][dt0][i].s] = 1;
	 	}
	 	if (ask(w) == dt) l = m + 1;
	 	else r = m - 1;
	 	for (int i = 0; i <= m; i++) {
			w[s[0][dt0][i].s] = 0;
	 	}
	}
	int ans0 = s[0][dt0][l].f;
	l = 0, r = sz(s[1][dt1]) - 1;
	while (l <= r) {
		int m = (l + r) / 2;
		for (int i = 0; i <= m; i++) {
			w[s[1][dt1][i].s] = 1;
	 	}
	 	if (ask(w) == dt) l = m + 1;
	 	else r = m - 1;
	 	for (int i = 0; i <= m; i++) {
			w[s[1][dt1][i].s] = 0;
	 	}
	}
	int ans1 = s[1][dt1][l].f;
	answer(ans0, ans1);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31