Submission #415716

#	Time	Username	Problem	Language	Result	Execution time	Memory
415716		_fractal	Highway Tolls (IOI18_highway)	C++14	7 / 100	330 ms	12432 KiB

highway

#include "highway.h"
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

vector<vector<pair<int, int>>> g;
vector<int> lmao;
long long cur;
int M;

int calc(int v, vector<pair<int, int>> t, int mid) {
	int tl = 1, tr = t.size() - 1, ans = v;
	vector<int> get(M, 0);
	while (tl <= tr) {
		int tm = tl + tr >> 1;
		for (auto &i : get) i = 0;
		for (int i = 1; i < t.size(); ++i)
			get[lmao[t[i].second]] = 1;
		for (int i = 1; i <= tm; ++i) {
			get[lmao[t[i].second]] = 0;
		}
		get[mid] = 0;
		if (ask(get) == cur) {
			ans = t[tm].second;
			tr = tm - 1;
		}
		else {
			tl = tm + 1;
		}
	}	
	return ans;
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
	M = U.size();
	vector<int> activ;
	vector<int> get(M, 0);
	vector<int> was(N, 0);
	g = vector<vector<pair<int, int>>> (N, vector<pair<int, int>>(0));
	cur = ask(get);
	lmao = vector<int>(N, 0);
	for (int i = 0; i < M; ++i) {
		g[V[i]].push_back({U[i], i});
		g[U[i]].push_back({V[i], i});
	}
	int tl = 0, tr = M, ans = -1;
	while (tl <= tr) {
		int tm = tl + tr >> 1;
		for (int i = 0; i < M; ++i)
			get[i] = (i <= tm ? 0 : 1);
		if (ask(get) == cur) {
			ans = tm;
			tr = tm - 1;
		}
		else {
			tl = tm + 1;
		}
	}
	queue<int> q;
	vector<int> d(N, -1), col(N, 0);
	vector<pair<int, int>> is[2];
	q.push(U[ans]), q.push(V[ans]);
	d[U[ans]] = d[V[ans]] = 0;
	col[U[ans]] = 0;
	col[V[ans]] = 1;
	while (q.size()) {
		int v = q.front();
		q.pop();
		is[col[v]].push_back({d[v], v});
		for (auto it : g[v]) {
			int to = it.first, c = it.second;
			if (d[to] == -1) {
				d[to] = d[v] + 1;
				col[to] = col[v];
				lmao[to] = c;
				q.push(to);
			}
		}
	}
	sort(is[0].begin(), is[0].end());
	sort(is[1].begin(), is[1].end());
	int a = calc(U[ans], is[0], ans);
	int b = calc(V[ans], is[1], ans);
	answer(a, b);
	return;
}

Compilation message (stderr)

highway.cpp: In function 'int calc(int, std::vector<std::pair<int, int> >, int)':
highway.cpp:16:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   16 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
highway.cpp:18:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for (int i = 1; i < t.size(); ++i)
      |                   ~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:49:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int tm = tl + tr >> 1;
      |            ~~~^~~~

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