Submission #1072529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072529		pawned	Highway Tolls (IOI18_highway)	C++17	12 / 100	106 ms	14648 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;
//	cout<<"lr, ds: "<<lr<<" "<<ds<<endl;
	// find all edges with distance ds-1 to ds
	queue<int> q;
	vi dist(N, 1e9);
	q.push(0);
	dist[0] = 0;
	vi goodid;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int y : adj[x]) {
			if (dist[y] == 1e9) {
				dist[y] = dist[x] + 1;
				if (dist[y] == ds)
					goodid.pb(conv[{min(x, y), max(x, y)}]);
				q.push(y);
			}
		}
	}
/*	cout<<"goodid: ";
	for (int x : goodid)
		cout<<x<<" ";
	cout<<endl;*/
	int K = goodid.size();
//	cout<<"K: "<<K<<endl;
	int low = 0;
	int high = K - 1;
	int res = -1;	// first pos so traffic includes res
	while (low <= high) {	// false, false, false, true, true, true
		int mid = (low + high) / 2;
		vi toask(M, 0);
		for (int i = 0; i <= mid; i++) {
			toask[goodid[i]] = true;
		}
		if (ask(toask) > lr) {
			res = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
//	cout<<"res: "<<res<<endl;
	int sp = -1;	// second vertex
	if (dist[edges[goodid[res]].fi] == ds)
		sp = edges[goodid[res]].fi;
	else
		sp = edges[goodid[res]].se;
//	cout<<"sp: "<<sp<<endl;
	answer(0, sp);
}

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