Submission #1195534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195534		aguss	Highway Tolls (IOI18_highway)	C++20	5 / 100	152 ms	327680 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << ": " << x << "\n";
vector<int> depth;
vector<pair<int, int>> nah;
vector<vector<int>> arr, neh;
void dfs(int node, int prev = -1){
	for(int &i : arr[node]){
		if(i == prev) continue;
		depth[i] = depth[node] + 1;
		nah.push_back({depth[i], neh[min(node, i)][max(node, i)]});
		dfs(i, node);
	}
}
int maxdepth(int a, int b){
	if(depth[a] > depth[b]) return a;
	return b;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	arr.assign(N, vector<int>());
	neh.assign(N, vector<int>(N));
	depth.assign(N, 0);
	int M = U.size();
	for(int i = 0; i < (int)U.size(); i++){
		if(U[i] > V[i]) swap(U[i], V[i]);
		neh[U[i]][V[i]] = i;
		arr[U[i]].push_back(V[i]);
		arr[V[i]].push_back(U[i]);
	}
	vector<int> vec(M, 0);
	long long x = ask(vec);
	dfs(0);
	for(int i = 0; i < M; i++){
		if(nah[i].first == x / A){
			vec[nah[i].second] = 1;
			if(ask(vec) != x){
				answer(0, maxdepth(U[nah[i].second], V[nah[i].second]));
				return;
			}
		}
	}
}

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