Submission #414468

#	Time	Username	Problem	Language	Result	Execution time	Memory
414468		Temmie	Highway Tolls (IOI18_highway)	C++17	0 / 100	14 ms	1008 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

typedef long long ll;

//namespace Q {
	//int N = 4;
	//std::vector <int> U = { 0, 0, 0 };
	//std::vector <int> V = { 1, 2, 3 };
	//int A = 1, B = 2;
	//int s = 2, e = 3;
//};

//ll ask(std::vector <int> v) {
	//ll ret = 
	//return 0;
//}

//void answer(int s, int t) {
	//std::cerr << "answered: (" << s << ", " << t << ")" << std::endl;
	//std::cerr << "answer was(" << Q::s << ", " << Q::e << ")" << std::endl;
//}

std::vector <std::vector <int>> g;

int dfs(int B, std::vector <int>& v, int length, int node = 0, int par = -1, int d = 0) {
	v[node] = 1;
	if (d == length) {
		ll now = ask(v);
		if (now == ll(B) * ll(length)) return node;
		return -1;
	}
	for (int x : g[node]) if (x != par) {
		int now = dfs(B, v, length, x, node, d + 1);
		if (now != -1) return now;
	}
	v[node] = 0;
	return -1;
}

void find_pair(int n, std::vector <int> U, std::vector <int> V, int A, int B) {
	g.resize(n);
	for (int i = 0; i < n - 1; i++) {
		g[U[i]].push_back(V[i]);
		g[V[i]].push_back(U[i]);
	}
	std::vector <int> v(n, 0);
	int length = ask(v) / ll(A);
	answer(1, dfs(B, v, length) + 1);
}

//int main() {
	
//}

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