Submission #613998

#	Time	Username	Problem	Language	Result	Execution time	Memory
613998		fvogel499	Highway Tolls (IOI18_highway)	C++17	0 / 100	297 ms	1172 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;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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;
}

int twoP(vector<int> part, vector<signed> edgeX, vector<signed> edgeY) {
    set<int> se;
    for (int i : part) {
        se.insert(i);
    }
    vi where;
    for (int i = 0; i < nbE; i++) {
        int u = se.count(edgeX[i]);
        int v = se.count(edgeY[i]);
        if ((u^v) == 1) {
            where.push_back(i);
        }
    }
    return caller(where);
}

void find_pair(const signed n, std::vector<signed> edgeX, std::vector<signed> edgeY, signed aK, signed bK) {
    nbE = sz(edgeX);
    int distVert = caller({});
    vi part [2];
    while (1) {
        part[0] = part[1] = {};
        for (int i = 0; i < n; i++) {
            if (rng()%2) {
                part[0].push_back(i);
            } else {
                part[1].push_back(i);
            }
        }
        int r = twoP(part[0], edgeX, edgeY);
        if (r%2 != distVert%2) {
            break;
        }
    }
    for (int i = 0; i < 2; i++) {
        while (sz(part[i]) != 1) {
            assert(!part[i].empty());
            vi lp, rp;
            for (int j : part[i]) {
                if (sz(lp) <= sz(rp)) {
                    lp.push_back(j);
                } else {
                    rp.push_back(j);
                }
            }
            int r = twoP(lp, edgeX, edgeY);
            if (r%2 != distVert%2) {
                part[i] = lp;
            } else {
                part[i] = rp;
            }
        }
    }
    int ansX = part[0][0];
    int ansY = part[1][0];
    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