Submission #566636

#	Time	Username	Problem	Language	Result	Execution time	Memory
566636		PiejanVDC	Highway Tolls (IOI18_highway)	C++17	5 / 100	24 ms	4368 KiB

highway

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

long long ask(const std::vector<int> &w);
void answer(int s, int t);

int m;
long long dist;

long long should;
map<pair<int,int>,int>id;

vector<int>adj[(int)9e4+5];

bool check(int i) {
	vector<int>A(m,0);
	A[i] = 1;
	if(ask(A) != should)
		return 1;
	return 0;
}

void dfs(int u, int d, int e = -1) {
	if(d == 1) {
		for(auto z : adj[u]) if(z != e) {
			if(check(id[{u,z}]))
				answer(0, z);
		}
		return;
	}
	for(auto z : adj[u]) if(z != e) {
		dfs(z, d-1, u);
	}
}

void find_pair(int n, vector<int>u, vector<int>v, int a, int b) {
	m = (int)u.size();
	vector<int>A((int)u.size());
	dist = ask(A) / a;	
	should = dist * a;
	for(int i = 0 ; i < m ; i++)
		adj[u[i]].push_back(v[i]), adj[v[i]].push_back(u[i]), id[{u[i],v[i]}] = id[{v[i], u[i]}] = i;
	dfs(0, dist);
}

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