Submission #614170

#	Time	Username	Problem	Language	Result	Execution time	Memory
614170		fvogel499	Highway Tolls (IOI18_highway)	C++17	51 / 100	285 ms	40008 KiB

highway

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

using namespace std;

#define int long long
#define vi vector<int>
#define pii pair<int, int>
#define f first
#define s second
#define sz(x) (int)((x).size())

const int siz = 1e6+40;
int nbE;
vector<pii> graph [siz];
int dist [2][siz];
int bounceOn [siz];
bool incl [2][siz];

int caller(vector<int> where) {
    vector<signed> u(nbE, 0);
    for (int i : where) {
        u[i] = 1; // se heavy
    }
    int r = ask(u);
    return r;
}

void bfs(const int t, int src) {
    queue<int> q;
    q.push(src);
    dist[t][src] = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (pii y : graph[x]) {
            if (dist[t][y.f] == -1) {
                dist[t][y.f] = dist[t][x] + 1;
                q.push(y.f);
                incl[t][y.s] = true;
            }
        }
    }
}

int whoIncrease(vi edgeSet, int refD) {
    int x = 0;
    for (int i = (1<<20); i; i /= 2) {
        int prop = x+i;
        if (prop > sz(edgeSet)) continue;
        vi where;
        for (int j = 0; j < prop; j++) {
            where.push_back(edgeSet[j]);
        }
        int r = caller(where);
        assert(r >= refD);
        if (r == refD) {
            x = prop;
        }
    }
    return edgeSet[x];
}

void find_pair(const signed n, std::vector<signed> edgeX, std::vector<signed> edgeY, signed aK, signed bK) {
    for (int i = 0; i < n; i++) graph[i].clear();
    nbE = sz(edgeX);
    int distVert = caller({});
    vi allEdges;
    for (int i = 0; i < nbE; i++) {
        allEdges.push_back(i);
    }
    const int magicEdge = whoIncrease(allEdges, distVert);
    for (int i = 0; i < nbE; i++) {
        graph[edgeX[i]].push_back({edgeY[i], i});
        graph[edgeY[i]].push_back({edgeX[i], i});
    }
    for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++) dist[i][j] = -1;
    for (int i = 0; i < nbE; i++) incl[0][i] = incl[1][i] = false;
    bfs(0, edgeX[magicEdge]);
    bfs(1, edgeY[magicEdge]);
    for (int i = 0; i < n; i++) {
        assert(dist[0][i] != -1 && dist[1][i] != -1);
        if (dist[0][i] < dist[1][i]) {
            dist[1][i] = -1;
        }
        else {
            dist[0][i] = -1;
        }
    }
    for (int i = 0; i < n; i++) bounceOn[i] = -1;
    for (int t = 0; t < 2; t++) {
        for (int i = 0; i < nbE; i++) if (i != magicEdge && incl[t][i]) {
            if (dist[t][edgeX[i]] == -1 || dist[t][edgeY[i]] == -1) continue;
            if (dist[t][edgeX[i]] > dist[t][edgeY[i]]) {
                bounceOn[edgeX[i]] = i;
            } else {
                bounceOn[edgeY[i]] = i;
            }
        }
    }
    vi between;
    for (int i = 0; i < nbE; i++) if (i != magicEdge) {
        if ((dist[0][edgeX[i]] == -1) != (dist[0][edgeY[i]] == -1)) {
            between.push_back(i);
        }
    }
    vi res;
    for (int t = 0; t < 2; t++) {
        vector<pair<int, int>> cand;
        for (int i = 0; i < n; i++) if (dist[t][i] != -1) {
            if (bounceOn[i] != -1) {
                cand.push_back({min(dist[t][edgeX[bounceOn[i]]], dist[t][edgeY[bounceOn[i]]]), bounceOn[i]});
            }
        }
        sort(cand.begin(), cand.end());
        int bs = -1;
        for (int i = (1<<20); i; i /= 2) {
            int prop = bs+i;
            if (prop > sz(cand)) continue;
            vi where;
            for (int j = prop; j < sz(cand); j++) {
                where.push_back(cand[j].s);
            }
            for (int j : between) {
                where.push_back(j);
            }
            int loc = caller(where);
            if (loc > distVert) {
                bs = prop;
            }
        }
        if (bs == -1 || bs == sz(cand)) {
            if (t == 0) {
                res.push_back(edgeX[magicEdge]);
            }
            else {
                res.push_back(edgeY[magicEdge]);
            }
            continue;
        }
        int loc;
        if (dist[t][edgeX[cand[bs].second]] > dist[t][edgeY[cand[bs].second]]) {
            loc = edgeX[cand[bs].second];
        } else {
            loc = edgeY[cand[bs].second];
        }
        res.push_back(loc);
    }
    answer(res[0], res[1]);
}

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