Submission #415746

#	Time	Username	Problem	Language	Result	Execution time	Memory
415746		_fractal	Highway Tolls (IOI18_highway)	C++14	100 / 100	616 ms	11776 KiB

highway

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

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

int calc(int v, vector<int> t) {
	int tl = 0, 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 = tm + 1; i < t.size(); ++i) {
			for (auto to : g[t[i]])
				get[to.second] = 1;	
		}
		if (ask(get) == cur) {
			ans = t[tm];
			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);
	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);
		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<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(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];
				q.push(to);
			}
		}
	}
	int a = calc(U[ans], is[0]);
	int b = calc(V[ans], is[1]);
	answer(a, b);
	return;
}

Compilation message (stderr)

highway.cpp: In function 'int calc(int, std::vector<int>)':
highway.cpp:15:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
highway.cpp:17:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for (int i = tm + 1; i < t.size(); ++i) {
      |                        ~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int tm = tl + tr >> 1;
      |            ~~~^~~~
highway.cpp:68:23: warning: unused variable 'c' [-Wunused-variable]
   68 |    int to = it.first, c = it.second;
      |                       ^

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