Submission #228918

#	Time	Username	Problem	Language	Result	Execution time	Memory
228918		anonymous	Highway Tolls (IOI18_highway)	C++14	100 / 100	295 ms	10872 KiB

highway

#include "highway.h"
#include <vector>
#include <queue>
#include <utility>
#include <iostream>
#define MAXN 90005
#define MAXE 130005
using namespace std;
 
queue <int> Q;
vector <pair<int,int> > adj[MAXN];
bool color[MAXN], vis[MAXN], inTree[MAXE];
int eid[MAXN];
vector <int> dist[2]; //ordered by dist
 
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    vector<int> w(M);
    for (int i = 0; i < M; ++i) {
        w[i] = 0;
    }
 
    long long base = ask(w);
 
    int lo = -1, hi = M-1; //find edge on shortest path
    while (lo + 1 != hi) {
        int mid = (lo + hi) >> 1;
        for (int i=0; i < M; i++) {
            w[i] = i <= mid;
        }
        if (ask(w) != base) {hi = mid;}
        else {lo = mid;}
    }
    Q.push(U[hi]);
    Q.push(V[hi]);
    color[V[hi]] = true;
    inTree[hi] = true;
    vis[U[hi]] = vis[V[hi]] = true;
    for (int i=0; i<M; i++) {
        adj[U[i]].push_back({V[i], i});
        adj[V[i]].push_back({U[i], i});
    }
 
    while (Q.size()) {
        int u = Q.front();
        Q.pop();
        dist[color[u]].push_back(u);
        for (auto v: adj[u]) {
            if (vis[v.first]) {continue;}
            vis[v.first] = true;
            inTree[v.second] = true;
            eid[v.first] = v.second;
            color[v.first] = color[u];
            Q.push(v.first);
        }
    }
    lo = 0, hi = dist[0].size()-1; 
    while (lo != hi) {
        int mid = (lo + hi + 1) >> 1;
        for (int i=0; i<M; i++) {
            w[i] = !inTree[i];
        }
        for (int i=dist[0].size()-1; i>=mid; i--) {
            w[eid[dist[0][i]]]=1;
        }
        if (ask(w) == base) {hi = mid-1;}
        else {lo = mid;}
    }
    int retA = dist[0][lo];
 
    lo = 0, hi = dist[1].size()-1;
    while (lo != hi) {
        int mid = (lo + hi + 1) >> 1;
        for (int i=0; i<M; i++) {
            w[i] = !inTree[i];
        }
        for (int i=dist[1].size()-1; i>=mid; i--) {
            w[eid[dist[1][i]]]=1;
        }
        if (ask(w) == base) {hi = mid-1;}
        else {lo = mid;}
    }
    int retB = dist[1][lo];
    answer(retA, retB);
}

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