제출 #1197912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197912		aguss	Highway Tolls (IOI18_highway)	C++20	12 / 100	276 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<pair<int, int>> depth;
vector<vector<pair<int, int>>> arr;
void dfs(int node, int prev = -1){
	for(const auto &i : arr[node]){
		if(i.first == prev) continue;
		depth[i.first] = {depth[node].first + 1, i.second};
		dfs(i.first, node);
	}	
}
int max_depht(int a, int b){
	if(depth[a].first > depth[b].first) return a;
	return b;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
	depth.assign(N, {0, 0});
	arr.assign(N, vector<pair<int, int>>());
	vector<int> pos_ans;
	vector<int> vec(U.size(), 0);
	long long dis = ask(vec);
	for(int i = 0; i < (int)U.size(); i++){
		arr[U[i]].push_back({V[i], i});
		arr[V[i]].push_back({U[i], i});
	}
	dfs(0);
	for(const auto &i : depth){
		if(i.first == dis / (long long)A){
			pos_ans.push_back(i.second);
		}
	}
	int l = 0, r = pos_ans.size();
	while(l + 1 < r){
		int m = (r + l) / 2;
		for(int i = l; i < m; i++){
			vec[pos_ans[i]] = 1;
		}
		long long aux = ask(vec);
		vec.assign(U.size(), 0);
		if(aux != dis){
			r = m;
			continue;
		}
		l = m;
	}
	answer(0, max_depht(U[pos_ans[l]], V[pos_ans[l]]));
}

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