Submission #416635

#	Time	Username	Problem	Language	Result	Execution time	Memory
416635		wiwiho	Highway Tolls (IOI18_highway)	C++14	5 / 100	3075 ms	10704 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;

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);
}

ll querye(int l, int r){
    vector<int> q(m);
    for(int i = l; i <= r; i++) q[i] = 1;
    return ask(q);
}

vector<int> vst;
void dfs(int now, int p, int e, int d, int no){
    pr[now] = p;
    pre[now] = e;
    dpt[now] = d;
    vst.eb(now);
    for(pii i : g[now]){
        if(i.F == p || i.S == no) continue;
        dfs(i.F, now, i.S, d + 1, no);
    }
}

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";
    
    int l = 0, r = m - 1;
    while(l < r){
        int mid = (l + r) / 2;
        if(querye(l, mid) != dis) r = mid;
        else l = mid + 1;
    }
    int e = l;
    dfs(U[e], U[e], -1, 0, e);

    ll dis1 = query(U[e], 0, (int)vst.size() - 1, vst);
    int len1 = (dis1 - dis) / (b - a);
    vector<int> tmp;
    for(int i : vst) if(dpt[i] == len1) tmp.eb(i);

    l = 0; r = (int)tmp.size() - 1;
    while(l < r){
        int mid = (l + r) / 2;
        if(query(U[e], l, mid, tmp) == dis1) r = mid;
        else l = mid + 1;
    }
    int v1 = tmp[l];

    vst.clear();
    dfs(V[e], V[e], -1, 0, e);
    ll dis2 = query(V[e], 0, (int)vst.size() - 1, vst);
    int len2 = (dis2 - dis) / (b - a);
    tmp.clear();
    for(int i : vst) if(dpt[i] == len2) tmp.eb(i);

    l = 0; r = (int)tmp.size() - 1;
    while(l < r){
        int mid = (l + r) / 2;
        if(query(V[e], l, mid, tmp) == dis2) r = mid;
        else l = mid + 1;
    }
    int v2 = tmp[l];
    //cerr << e << " " << U[e] << " " << V[e] << " " << v1 << " " << v2 << "\n";
    
    answer(v1, v2);
}

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