Submission #248402

#	Time	Username	Problem	Language	Result	Execution time	Memory
248402		kostia244	Highway Tolls (IOI18_highway)	C++17	18 / 100	165 ms	10392 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 m;
vector<int> c;
vector<int> res;
vector<array<int, 2>> g[maxn];
int D, a, b;
void dfs(int v, int p, int h = 0) {
	for(auto [i, id] : g[v]) if(i != p) {
		if(h+1 == D) c.push_back(id), res.push_back(i);
		dfs(i, v, h+1);
	}
}
bool go(vector<int> c, int p) {
	vector<int> w(m);
	for(int i = 0; i <= p; i++) w[c[i]] = 1;
	return ask(w) == a*1ll*D; 
}
bool gob(vector<int> c, int p) {
	vector<int> w(m);
	for(int i = 0; i <= p; i++) w[c[i]] = 1;
	return ask(w) == b*1ll*D; 
}
void find_pair(int n, std::vector<int> U, std::vector<int> V, int A, int B) {
	a = A, b = B;
	m = U.size();
	if(m != n-1) return;
	int s3 = 1;
	for(int i = 0; i < U.size(); i++) {
		s3 &= U[i] == i && V[i] == i+1;
		g[U[i]].push_back({V[i], i});
		g[V[i]].push_back({U[i], i});
	}
	D = ask(vector<int>(m))/A;
	if(s3) {
		for(int i = 0; i < m; i++)
			c.push_back(i);
		int ans = -1;
		for(int z = 1<<17; z>>=1;)
			if(ans+z < c.size() && go(c, ans+z)) ans += z;
		int ans1 = ans++;
		for(int z = 1<<17; z>>=1;)
			if(ans1+z < c.size() && !gob(c, ans1+z)) ans1 += z;
		answer(ans, ans1+2);
		return;
	}
	dfs(0, 0, 0);
	int ans = -1;
	for(int z = 1<<17; z>>=1;)
		if(ans+z < c.size() && go(c, ans+z)) ans += z;
	answer(0, res[ans+1]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < U.size(); i++) {
                 ~~^~~~~~~~~~
highway.cpp:44:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ans+z < c.size() && go(c, ans+z)) ans += z;
       ~~~~~~^~~~~~~~~~
highway.cpp:47:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ans1+z < c.size() && !gob(c, ans1+z)) ans1 += z;
       ~~~~~~~^~~~~~~~~~
highway.cpp:54:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(ans+z < c.size() && go(c, ans+z)) ans += z;
      ~~~~~~^~~~~~~~~~

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