제출 #952023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
952023		Pikachu	통행료 (IOI18_highway)	C++17	5 / 100	167 ms	12728 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

const int maxn = 1e5 + 10;
int n, m;
int best;
vector<pair<int,int> > adj[maxn];
int d[2][maxn];
int dis[maxn];
int oe[maxn];
vector<pair<int,int> > edge[2];
int res[2];

void BFS(int u, int d[])
{
    queue<int> q;
    d[u] = 0;
    q.push(u);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (pair<int,int> p : adj[cur]) {
            if (d[p.first] == -1) {
                d[p.first] = d[cur] + 1;
                q.push(p.first);
            }
        }
    }
}

int findfirstedge()
{
    int l = 0;
    int r = m - 1;
    int ans = -1;
    best = ask(vector<int>(m, 0));
    while (l <= r) {
        int mid = (l + r) >> 1;
        vector<int> mim(m, 0);
        for (int i = 0; i <= mid; i++) mim[i] = 1;
        if (ask(mim) != best) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return ans;
}

void find_pair(int n, vector<int> U, vector<int> V, int A, int B) 
{
    ::n = n;
    m = U.size();
    for (int i = 0; i < m; i++) {
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
    int e = findfirstedge();
    memset(d, -1, sizeof d);
    int u = U[e], v = V[e];
    BFS(u, d[0]);
    BFS(v, d[1]);
    for (int i = 0; i < n; i++) {
        if (d[0][i] == d[1][i]) {
            oe[i] = -1;
            continue;
        }
        oe[i] = d[0][i] > d[1][i];
        dis[i] = min(d[0][i], d[1][i]);
        adj[i].clear();
    }
    for (int i = 0; i < m; i++) {
        int &u = U[i], &v = V[i];
        if (oe[u] == -1 || oe[v] == -1) continue;
        if (oe[u] == oe[v]) {
            if (dis[u] == dis[v]) continue;
            if (dis[u] > dis[v]) swap(u, v);
            edge[oe[u]].push_back({dis[v], i});
        }
    }
    for (int id = 0; id < 2; id++) {
        sort(edge[id].begin(), edge[id].end());
        int l = 0;
        int r = edge[id].size() - 1;
        int ans = edge[id].size();
        while (l <= r) {
            int mid = (l + r) >> 1;
            vector<int> mim(m, 0);
            for (int i = mid; i < (int)edge[id].size(); i++) {
                mim[edge[id][i].second] = 1;
            }
            if (ask(mim) != best) {
                l = mid + 1;
            }
            else {
                r = mid - 1;
                ans = mid;
            }
        }
        if (ans == 0) {
            res[id] = (id == 0 ? u : v);
        }
        else {
            res[id] = V[edge[id][ans - 1].second];
        }
    }
    answer(res[0], res[1]);
}

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