Submission #416613

#	Time	Username	Problem	Language	Result	Execution time	Memory
416613		wiwiho	Highway Tolls (IOI18_highway)	C++14	6 / 100	120 ms	14040 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>

#define eb emplace_back
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define mp make_pair
#define F first
#define S second
#define pob pop_back()
#define iter(a) a.begin(), a.end()

using namespace std;

typedef long long ll;

using pll = pair<ll, ll>;
using pii = pair<int, int>;

int n;
int m;
vector<vector<pii>> g;
vector<int> pr, pre, dpt;
vector<int> leaf;

ll query(int rt, int to){
    vector<int> q(m);
    while(to != rt){
        q[pre[to]] = 1;
        to = pr[to];
    }
    return ask(q);
}

ll query(int rt, int l, int r, vector<int>& v){
    vector<int> q(m);
    vector<int> tos;
    for(int i = l; i <= r; i++) tos.eb(v[i]);
    for(int to : tos){
        while(to != rt){
            q[pre[to]] = 1;
            to = pr[to];
        }
    }
    return ask(q);
}

int up(int from, int x){
    while(x--){
        from = pr[from];
    }
    return from;
}

void dfs(int now, int p, int e, int d){
    pr[now] = p;
    pre[now] = e;
    dpt[now] = d;
    bool child = false;
    for(pii i : g[now]){
        if(i.F == p) continue;
        dfs(i.F, now, i.S, d + 1);
        child = true;
    }
    if(!child) leaf.eb(now);
}

void find_pair(int N, vector<int> U, vector<int> V, int a, int b) {
    n = N;
    m = U.size();
    assert(m == n - 1);

    g.resize(n);
    pr.resize(n);
    pre.resize(n);
    dpt.resize(n);
    for(int i = 0; i < m; i++){
        int u = U[i], v = V[i];
        g[u].eb(mp(v, i));
        g[v].eb(mp(u, i));
    }

    vector<int> XD(m);
    ll dis = ask(XD);
    //cerr << dis << "\n";

    dfs(0, 0, -1, 0);
    int l = 0, r = (int)leaf.size() - 1;
    while(l < r){
        int mid = (l + r) / 2;
        if(query(0, l, mid, leaf) != dis) r = mid;
        else l = mid + 1;
    }
    int tmp = leaf[l];

    l = 0, r = dpt[tmp];
    ll dis2 = query(0, tmp);
    while(l < r){
        int mid = (l + r + 1) / 2;
        //cerr << "test " << mid << " " << up(tmp, mid) << " " << query(0, up(tmp, mid)) << "\n";
        if(query(0, up(tmp, mid)) != dis2) r = mid - 1;
        else l = mid;
    }

    int v1 = up(tmp, l);
    //cerr << "v1 " << v1 << " " << tmp << " " << l  << "\n";
    leaf.clear();
    dfs(v1, v1, -1, 0);
    vector<int> v;
    for(int i = 0; i < n; i++){
        if(dpt[i] == dis / a) v.eb(i);
    }

    l = 0, r = (int)v.size() - 1;
    while(l < r){
        int mid = (l + r) / 2;
        if(query(v1, l, mid, v) != dis) r = mid;
        else l = mid + 1;
    }

    int v2 = v[l];
    
    answer(v1, v2);
}

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