Submission #295397

#	Time	Username	Problem	Language	Result	Execution time	Memory
295397		SeDunion	Highway Tolls (IOI18_highway)	C++17	100 / 100	522 ms	13516 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int M;
const int MAXN = 2e5;
vector<pair<int,int>> g[MAXN];
vector<int> h[2],W;

ll dist;
// map<int,int> id[MAXN];

int find(vector<int>v) {
	int l = 0, r = v.size()-1;
	while (l <= r) {
		int m = (l + r) >> 1;
		for (int i = 0 ; i < M ; ++ i) {
			W[i] = 0;
		}
		for (int i = m ; i < v.size() ; ++ i) {
			for (auto [to,qaz] : g[v[i]]) {
				W[qaz] = 1;
				// W[id[V[i]][to]] = 1;
			}
		}
		if (ask(W)!=dist)l=m+1;
		else r=m-1;
	}
	return v[l-1];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	M = U.size();
	for (int i = 0 ; i < M ; ++ i) {
		g[U[i]].push_back ({V[i], i});
		g[V[i]].push_back ({U[i], i});
		// id[U[i]][V[i]]=id[V[i]][U[i]]=i;
	}
	W = vector<int>(M,0);
	dist = ask(W);
	int l = 0, r = M - 1;
	while (l <= r) {
		int m = (l + r) >> 1;
		for (int i = 0 ; i < M ; ++ i) {
			W[i] = i <= m;
		}
		if (ask(W) == dist) {
			l = m + 1;
		} else {
			r = m - 1;
		}
	}
	int u = U[l], v = V[l];
																	// cout<<u<<" <-> "<<v<<'\n';
	queue<pair<int,int>>q;
	vector<int>d(N,MAXN);
	q.push({u,0});
	q.push({v,1});
	d[u]=d[v]=0;
	while(q.size()) {
		int v, t;
		tie (v, t) = q.front(); q.pop();
		h[t].push_back (v);
		for (auto [to, i] : g[v]) if (d[to] > d[v] + 1) {
			d[to] = d[v] + 1;
			q.push({to,t});
		}
	}
														// cout<<find(h[0])<<" >-< " << find(h[1]) << "\n";
	answer (find(h[0]),find(h[1]));
}

Compilation message (stderr)

highway.cpp: In function 'int find(std::vector<int>)':
highway.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for (int i = m ; i < v.size() ; ++ i) {
      |                    ~~^~~~~~~~~~

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