| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1158941 | PagodePaiva | 통행료 (IOI18_highway) | C++17 | 0 ms | 0 KiB |
#include "highway.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 90010;
vector <pair <ll, ll>> g[N];
pair <ll, ll> especial;
vector <ll> query;
pair <ll, ll> pai[N];
ll h[N];
ll t1;
vector <array <ll, 3>> arestas;
void dfs(ll v, ll p){
for(auto [x, idx] : g[v]){
if(x == p) continue;
query[idx] = 1;
dfs(x, v);
}
return;
}
void dfs2(ll v, ll p){
for(auto [x, idx] : g[v]){
if(x == p) continue;
h[x] = h[v]+1;
pai[x] = {v, idx};
if(h[x] == t1) arestas.push_back({x, v, idx});
dfs2(x, v);
}
return;
}
void find_pair(int n, std::vector<int> u, std::vector<int> v, int A, int B) {
ll m = u.size();
for(ll i = 0;i < m;i++){
ll a = u[i], b = v[i];
g[a].push_back({b, i});
g[b].push_back({a, i});
}
for(ll i = 0;i < m;i++){
query.push_back(0);
}
ll h = ask(query)/A;
ll l = 0, r = m-1;
while(l < r){
ll mid = (l+r)/2;
for(ll i = l;i <= mid;i++){
query[i] = 1;
}
ll t = ask(query);
for(ll i = l;i <= mid;i++){
query[i] = 0;
}
if(t > h*A){
r = mid;
}
else{
l = mid+1;
}
}
especial = {u[l], v[l]};
dfs(u[l], v[l]);
// cout << u[l] << ' ' << v[l] << endl;
ll S = ask(query);
t1 = (S-A*h)/(B-A);
//// cout << t1 << endl;
ll ll = l;
for(ll i = 0;i < m;i++){
query[i] = 0;
}
pair <ll, ll> resposta;
if(t1 == 0) resposta.first = u[ll];
else{
dfs2(u[ll], v[ll]);
l = 0; r = arestas.size()-1;
// cout << t1 << endl;
for(auto [a, b, c] : arestas){
// cout << a << ' ' << b << ' ' << c << endl;
}
while(l < r){
ll mid = (l+r)/2;
for(ll i = l;i <= mid;i++){
query[arestas[i][2]] = 1;
}
ll t = ask(query);
for(ll i = l;i <= mid;i++){
query[arestas[i][2]] = 0;
}
// cout << t << endl;
if(t > h*A){
r = mid;
}
else{
l = mid+1;
}
}
resposta.first = arestas[l][0];
}
//// cout << resposta.first << endl;
arestas.clear();
t1 = h-t1-1;
swap(u[ll], v[ll]);
// cout << u[ll] << ' ' << v[ll] << endl;
if(t1 == 0) resposta.second = u[ll];
else{
dfs2(u[ll], v[ll]);
l = 0; r = arestas.size()-1;
while(l < r){
ll mid = (l+r)/2;
for(ll i = l;i <= mid;i++){
query[arestas[i][2]] = 1;
}
ll t = ask(query);
for(ll i = l;i <= mid;i++){
query[arestas[i][2]] = 0;
}
if(t > h*A){
r = mid;
}
else{
l = mid+1;
}
}
resposta.second = arestas[l][0];
}
// cout << resposta.first << ' ' << resposta.second << endl;
answer(resposta.first, resposta.second);
return;
}