Submission #613972

#	Time	Username	Problem	Language	Result	Execution time	Memory
613972		fvogel499	Highway Tolls (IOI18_highway)	C++17	0 / 100	303 ms	262144 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;
vi graph [siz];
int dist [2][siz];
int bounceOn [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 dfs(int t, int x, int d, int p) {
    dist[t][x] = d;
    for (int y : graph[x]) {
        if (y == p) continue;
        dfs(t, y, d+1, x);
    }
}

int whoIncrease(vi edgeSet, int refD) {
    while (sz(edgeSet) != 1) {
        assert(!edgeSet.empty());
        vi leftSet, rightSet;
        for (int i : edgeSet) {
            if (sz(leftSet) <= sz(rightSet)) {
                leftSet.push_back(i);
            } else {
                rightSet.push_back(i);
            }
        }
        int loc = caller(leftSet);
        assert(loc >= refD);
        if (loc > refD) {
            edgeSet = leftSet;
        }
        else {
            edgeSet = rightSet;
        }
    }
    return edgeSet[0];
}

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++) if (i != magicEdge) {
        graph[edgeX[i]].push_back(edgeY[i]);
        graph[edgeY[i]].push_back(edgeX[i]);
    }
    for (int i = 0; i < 2; i++) for (int j = 0; j < n; j++) dist[i][j] = -1;
    dfs(0, edgeX[magicEdge], 0, -1);
    dfs(1, edgeY[magicEdge], 0, -1);
    vi edgesOnSideX;
    for (int i = 0; i < nbE; i++) if (i != magicEdge) {
        if (dist[0][edgeX[i]] == -1 || dist[0][edgeY[i]] == -1) continue;
        assert(dist[0][edgeX[i]] != -1 && dist[0][edgeY[i]] != -1);
        edgesOnSideX.push_back(i);
    }
    int increasedSideXDist = caller(edgesOnSideX);
    assert((increasedSideXDist-distVert)%(bK-aK) == 0);
    int distX = (increasedSideXDist-distVert)/(bK-aK);
    int distY = (distVert/aK)-1-distX;
    assert(0 <= distY);
    for (int i = 0; i < n; i++) bounceOn[i] = -1;
    for (int i = 0; i < nbE; i++) if (i != magicEdge) {
        if (dist[0][edgeX[i]] == -1 || dist[0][edgeY[i]] == -1) continue;
        assert(dist[0][edgeX[i]] != -1 && dist[0][edgeY[i]] != -1);
        if (dist[0][edgeX[i]] > dist[0][edgeY[i]]) {
            bounceOn[edgeX[i]] = i;
        } else {
            assert(dist[0][edgeX[i]] < dist[0][edgeY[i]]);
            bounceOn[edgeY[i]] = i;
        }
    }
    for (int i = 0; i < nbE; i++) if (i != magicEdge) {
        if (dist[1][edgeX[i]] == -1 || dist[1][edgeY[i]] == -1) continue;
        assert(dist[1][edgeX[i]] != -1 && dist[1][edgeY[i]] != -1);
        if (dist[1][edgeX[i]] > dist[1][edgeY[i]]) {
            bounceOn[edgeX[i]] = i;
        } else {
            assert(dist[1][edgeX[i]] < dist[1][edgeY[i]]);
            bounceOn[edgeY[i]] = i;
        }
    }
    for (int i = 0; i < n; i++) {
        if (i == edgeX[magicEdge]) continue;
        if (i == edgeY[magicEdge]) continue;
        assert(bounceOn[i] != -1);
    }
    int ansX = edgeX[magicEdge];
    if (distX > 0) {
        vi possX;
        for (int i = 0; i < n; i++) if (dist[0][i] == distX) {
            assert(bounceOn[i] != -1);
            assert(bounceOn[i] != magicEdge);
            possX.push_back(bounceOn[i]);
        }
        assert(!possX.empty());
        int loc = whoIncrease(possX, distVert);
        if (dist[0][edgeX[loc]] > dist[0][edgeY[loc]]) {
            ansX = edgeX[loc];
        } else {
            ansX = edgeY[loc];
        }
    }
    int ansY = edgeY[magicEdge];
    if (distY > 0) {
        vi possY;
        for (int i = 0; i < n; i++) if (dist[1][i] == distY) {
            assert(bounceOn[i] != -1);
            assert(bounceOn[i] != magicEdge);
            possY.push_back(bounceOn[i]);
        }
        assert(!possY.empty());
        int loc = whoIncrease(possY, distVert);
        if (dist[1][edgeX[loc]] > dist[1][edgeY[loc]]) {
            ansY = edgeX[loc];
        } else {
            ansY = edgeY[loc];
        }
    }
    cout << ansX << " " << ansY << endl;
    answer(ansX, ansY);
}

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