제출 #1055657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055657		efishel	통행료 (IOI18_highway)	C++17	51 / 100	101 ms	18676 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 1.3E5+16;
vii adj[MAXN];
bool vis[MAXN];
ll toPar[MAXN];

vll ord;
void dfs (ll u) {
    vis[u] = true;
    for (auto [v, id] : adj[u]) {
        if (vis[v]) continue;
        dfs(v);
        toPar[v] = id;
    }
    ord.push_back(u);
}

void find_pair (int n, vi us, vi vs, int a, int b) {
    ll m = us.size();
    for (ll i = 0; i < m; i++) {
        adj[us[i]].push_back({ vs[i], i });
        adj[vs[i]].push_back({ us[i], i });
    }
    ll dis = ask(vi(m, 0));
    // {ll l = 0, r = n;
    // while (l+1 < r) {
    //     ll mid = (l+r)>>1;
    //     vi vask(m);
    //     for (ll i = 0; i < m; i++) vask[i] = i < mid;
    //     if (ask(vask) == dis) {
    //         ;
    //     }
    // }}
    // todo: make tree
    vi askMask(m, 0);
    dfs(0);
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    ll u1 = -15, u2 = -15;
    {ll l = -1, r = m-1;
    // l es normal
    // r lo corta
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask = askMask;
        for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
        if (ask(vask) == dis)
            l = mid;
        else
            r = mid;
    }
    u1 = ord[r];}
    fill(vis, vis+MAXN, false);
    ord.clear();
    dfs(u1);
    // for (ll i : ord) cout << i << ' ';
    // cout << " ord\n";
    {ll l = -1, r = m-1;
    // l es normal
    // r lo corta
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        vi vask = askMask;
        for (ll i = 0; i <= mid; i++) vask[toPar[ord[i]]] = 1;
        if (ask(vask) == dis)
            l = mid;
        else
            r = mid;
    }
    // cout << "l, r: " << l << ' ' << r << '\n';
    // cout << "ord[l, r]: " << ord[l] << ' ' << ord[r] << '\n';
    u2 = ord[r];}
    // cout << "u1 " << u1 << '\n';
    // cout << "u2 " << u2 << '\n';
    answer(u1, u2);
}

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