제출 #1055661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055661		efishel	통행료 (IOI18_highway)	C++17	51 / 100	149 ms	35124 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];
vii adjT[MAXN];
bool vis[MAXN];
ll toPar[MAXN];

vll ord;
void dfs (ll u) {
    vis[u] = true;
    for (auto [v, id] : adjT[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));
    vi askMask(m, 0);
    ll src1 = -15, src2 = -15;
    {ll l = -1, r = m-1;
    while (l+1 < r) {
        ll mid = (l+r)>>1;
        askMask = vi(m, 0);
        for (ll i = 0; i <= mid; i++) askMask[i] = 1;
        if (ask(askMask) == dis)
            l = mid;
        else
            r = mid;
    }
    askMask = vi(m, 0);
    for (ll i = 0; i <= l; i++) askMask[i] = 1;
    src1 = us[r];
    src2 = vs[r];
    queue <ll> q;
    vector <char> vis(n, false);
    vis[src1] = true; q.push(src1);
    vis[src2] = true; q.push(src2);
    adjT[src1].push_back({ src2, r });
    adjT[src2].push_back({ src1, r });
    while (q.size()) {
        ll u = q.front(); q.pop();
        for (auto [v, id] : adj[u]) {
            if (vis[v]) continue;
            vis[v] = true; q.push(v);
            adjT[u].push_back({ v, id });
            adjT[v].push_back({ u, id });
        }
    }}
    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