Submission #1072564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072564		pawned	Highway Tolls (IOI18_highway)	C++17	51 / 100	200 ms	19764 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;
map<ii, int> conv;	// id of each edge

ll A, B;

ll lr, ds;

int findOther(int r) {	// find other endpoint from root
	queue<int> q;
	vi dist(N, 1e9);
	q.push(r);
	dist[r] = 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;
//		cout<<"at "<<mid<<endl;
		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;
	return sp;
}

void find_pair(int N_g, vi U_g, vi V_g, int A_g, int B_g) {
	N = N_g;
	M = U_g.size();
	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);
	lr = ask(tq);
	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;
	int D = 0;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		D = max(D, dist[x]);
		for (int y : adj[x]) {
			if (dist[y] == 1e9) {
				dist[y] = dist[x] + 1;
				q.push(y);
			}
		}
	}
	vi edgec[D + 1];
	// edgec[i] stores all id of edges w/ (deeper) depth i
	for (ii p : edges) {
		edgec[max(dist[p.fi], dist[p.se])].pb(conv[p]);
	}
	int low = 1;
	int high = D;
	int dr = -1;	// [dr-1, dr] is deepest w/ selected edge
	while (low <= high) {	// true, true, true, false, false, false
		// add all dr and above, see if has selected
		int mid = (low + high) / 2;
		vi tq(M, 0);
		for (int i = mid; i <= D; i++) {
			for (int x : edgec[i])
				tq[x] = 1;
		}
		if (ask(tq) > lr) {
			dr = mid;
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}
//	cout<<"dr: "<<dr<<endl;
	low = 0;
	high = edgec[dr].size() - 1;
	int dt = -1;	// edgec[dr][dt] is the first selected
	while (low <= high) {	// false, false, false, true, true, true
		int mid = (low + high) / 2;
		vi tq(M, 0);
		for (int i = 0; i <= mid; i++) {
			tq[edgec[dr][i]] = 1;
		}
		if (ask(tq) > lr) {
			dt = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}
//	cout<<"dt: "<<dt<<endl;
	int cid = edgec[dr][dt];
//	cout<<"cid: "<<cid<<endl;
	int s1 = -1;
	if (dist[edges[cid].fi] > dist[edges[cid].se])
		s1 = edges[cid].fi;
	else
		s1 = edges[cid].se;
//	cout<<"s1: "<<s1<<endl;
	int s2 = findOther(s1);
	answer(s1, s2);
}

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