Submission #248588

#	Time	Username	Problem	Language	Result	Execution time	Memory
248588		kostia244	Highway Tolls (IOI18_highway)	C++17	90 / 100	382 ms	19576 KiB

highway

#include "highway.h"
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1<<17;
using ll = long long;
int n, m;
vector<int> c, res, d, edges;
vector<array<int, 2>> g[maxn], G[maxn], edgelist;
int D, a, b;
bool go(vector<int> c, int p) {
	vector<int> w(m, 0);
	for(int i = 0; i <= p; i++) w[c[i]] = 1;
	int res = ask(w) == a*1ll*D;
	//for(auto &i : w) cout << i;cout << " " << res << endl;
	return res;
}
int findroot() {
	int p = -1;
	vector<int> al;
	for(int i = 0; i < m; i++) al.push_back(i);
	for(int i = 1<<17; i>>=1;)
		if(p+i < m && go(al, p+i)) p += i;
	return edgelist[++p][0];
}
void reroot(int root) {
	//cout << "Root at " << root << " Faggot!\n";
	queue<int> q;
	d = vector<int>(n, 1<<30);
	for(int i = 1; i <= n; i++) g[i].clear();
	q.push({root});
	d[root] = 0;
	while(!q.empty()) {
		int v = q.front();
		q.pop();
		for(auto [u, id] : G[v]) {
			ll nd = d[v] + 1;
			if(d[u] > nd) {
				g[u].push_back({v, id});
				g[v].push_back({u, id});
				d[u] = nd;
				q.push(u);
			}
		}
	}
	for(auto &[x, y] : edgelist) if(d[x] < d[y]) swap(x, y);
	sort(edges.begin(), edges.end(), [](auto _i, auto _j) {
		auto i = edgelist[_i], j = edgelist[_j];
		return array<int, 2>{d[i[0]], d[i[1]]} > array<int, 2>{d[j[0]], d[j[1]]};
	});
	//for(auto &i : edges) cout << edgelist[i][0] << " " << edgelist[i][1] << '\n';
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	n = N;
	a = A, b = B;
	m = U.size();
	for(int i = 0; i < m; i++) edges.push_back(i);
	int s3 = 1;
	for(int i = 0; i < U.size(); i++) {
		s3 &= U[i] == i && V[i] == i+1;
		edgelist.push_back({U[i], V[i]});
		G[U[i]].push_back({V[i], i});
		G[V[i]].push_back({U[i], i});
	}
	D = ask(vector<int>(m))/A;
	reroot(findroot());
	int p = -1;
	for(int i = 1<<17; i>>=1;)
		if(p+i < m && go(edges, p+i)) p += i;
	int s = edgelist[edges[++p]][0];
	
	reroot(s);
	p = -1;
	for(int i = 1<<17; i>>=1;)
		if(p+i < m && go(edges, p+i)) p += i;
	int t = edgelist[edges[++p]][0];
	//cout << s << " " << t << endl;
	answer(s, t);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < U.size(); i++) {
                 ~~^~~~~~~~~~

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