Submission #1158943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158943		PagodePaiva	Highway Tolls (IOI18_highway)	C++17	51 / 100	342 ms	327680 KiB

highway

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

using namespace std;

const lg N = 90010;
vector <pair <lg, lg>> g[N];
pair <lg, lg> especial;
vector <int> query;
pair <lg, lg> pai[N];
lg h[N];
lg t1;
vector <array <lg, 3>> arestas;

void dfs(lg v, lg p){
    for(auto [x, idx] : g[v]){
        if(x == p) continue;
        query[idx] = 1;
        dfs(x, v);
    }
    return;
}

void dfs2(lg v, lg 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) {
    lg m = u.size();
    for(lg i = 0;i < m;i++){
        lg a = u[i], b = v[i];
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    for(lg i = 0;i < m;i++){
        query.push_back(0);
    }
    lg h = ask(query)/A;
    lg l = 0, r = m-1;
    while(l < r){
        lg mid = (l+r)/2;
        for(lg i = l;i <= mid;i++){
            query[i] = 1;
        }
        lg t = ask(query);
        for(lg 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;
    lg S = ask(query);
    t1 = (S-A*h)/(B-A);
    //// cout << t1 << endl;
    lg ll = l;
    for(lg i = 0;i < m;i++){
        query[i] = 0;
    }
    pair <lg, lg> 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){
            lg mid = (l+r)/2;
            for(lg i = l;i <= mid;i++){
                query[arestas[i][2]] = 1;
            }
            lg t = ask(query);
            for(lg 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){
            lg mid = (l+r)/2;
            for(lg i = l;i <= mid;i++){
                query[arestas[i][2]] = 1;
            }
            lg t = ask(query);
            for(lg 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;
}

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