Submission #816403

#	Time	Username	Problem	Language	Result	Execution time	Memory
816403		Jarif_Rahman	Highway Tolls (IOI18_highway)	C++17	12 / 100	203 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, m;
ll A, B;
vector<vector<pair<int, int>>> graph;
vector<int> depth, p, pe;

void dfs(int nd, int dad, int dad_edge, int d){
    p[nd] = dad;
    depth[nd] = d;
    pe[nd] = dad_edge;
    for(auto [x, i]: graph[nd]) if(x != dad) dfs(x, nd, i, d+1);
}

void find_pair(int _n, vector<int> U, vector<int> V, int _A, int _B){
    swap(n, _n);
    int m = U.size();
    A = _A, B = _B;
    graph.resize(n);
    depth.resize(n);
    p.resize(n);
    pe.resize(n, -1);

    for(int i = 0; i < m; i++){
        graph[U[i]].pb({V[i], i});
        graph[V[i]].pb({U[i], i});
    }

    dfs(0, -1, -1, 0);
    vector<int> o(n);
    for(int i = 0; i < n; i++) o[i] = i;
    sort(o.begin(), o.end(), [&](int a, int b){
        return depth[a] > depth[b];
    });

    ll def = ask(vector<int>(m, 0));

    bool subtask3 = 1;
    for(int i = 0; i < n-1; i++) if(U[i] != i || V[i] != i+1) subtask3 = 0;

    if(subtask3){
        int s, t;
        {
            int a = 0, b = m-1;
            while(a < b){
                int md = (a+b+1)/2;
                vector<int> w(m, 0);
                for(int i = 0; i <= md; i++) w[i] = 1;
                ll x = ask(w);
                if(x > def) a = md;
                else b = md-1;
            }
            t = a+1;
        }
        {
            int a = 0, b = m-1;
            while(a < b){
                int md = (a+b+1)/2;
                vector<int> w(m, 0);
                for(int i = m-1; i >= md; i--) w[i] = 1;
                ll x = ask(w);
                if(x > def) b = md-1;
                else a = md;
            }
            s = a;
        }
        answer(s, t);
        return;
    }

    int a = 0, b = n-1;
    while(a < b){
        int md = (a+b)/2;
        vector<int> w(m, 0);
        for(int i = 0; i <= md; i++) if(pe[o[i]] != -1) w[pe[o[i]]] = 1;
        ll x = ask(w);
        if(x > def) b = md;
        else a = md+1;
    }

    answer(0, o[a]);
}

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