Submission #1072538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072538		pawned	Highway Tolls (IOI18_highway)	C++17	6 / 100	84 ms	14064 KiB

highway

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "highway.h"

const int MAX = 1e5 + 5;

int N, M;

vi adj[MAX];

vector<ii> edges;

ll A, B;

void find_pair(int N_g, vi U_g, vi V_g, int A_g, int B_g) {
	N = N_g;
	int M = U_g.size();
	map<ii, int> conv;	// id of each edge
	for (int i = 0; i < M; i++) {
		adj[U_g[i]].pb(V_g[i]);
		adj[V_g[i]].pb(U_g[i]);
		edges.pb({min(U_g[i], V_g[i]), max(U_g[i], V_g[i])});
		conv[edges.back()] = i;
	}
	A = A_g; B = B_g;
	vi tq(M, 0);
	ll lr = ask(tq);
	ll ds = lr / A;
	int low = 0;
	int high = M - 1;
	int res = -1;	// first edge that's part
	while (low <= high) {	// false, false, false, true, true, true
		int mid = (low + high) / 2;
		vi tq(M, 0);
		for (int j = 0; j <= mid; j++) {
			tq[j] = 1;
		}
		if (ask(tq) > lr) {
			res = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
	answer(res, res + ds);
}

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