Submission #286379

#	Time	Username	Problem	Language	Result	Execution time	Memory
286379		NONAME	통행료 (IOI18_highway)	C++14	51 / 100	224 ms	262148 KiB

highway

#include "highway.h"

int m;
int res[2];
std::vector <int> w;
std::vector <std::pair <int, int> > g[(int)(1e5)], vec;

void dfs(int ve, int pr) {
    for (auto to : g[ve]) {
        if (to.first == pr)
            continue;

        vec.push_back(to);
        dfs(to.first, ve);
    }
}

int poisk(long long total, long long B) {
    int l = 0, r = (int)(vec.size()) - 1;
    while (l < r) {
        int md = (l + r) >> 1;

        for (int i = 1; i < (int)(vec.size()); ++i)
            w[vec[i].second] = (i <= md);

        if (ask(w) == total * B) r = md;
            else l = md + 1;
    }
    return l;
}

void find_pair (int n, std::vector <int> u, std::vector <int> v, int A, int B) {
    m = (int)(u.size());

    for (int i = 0; i < m; ++i) {
        g[u[i]].push_back(std::make_pair(v[i], i));
        g[v[i]].push_back(std::make_pair(u[i], i));
    }

    w.assign(m, 0);
    long long total = ask(w) / A;

    int s = 0;
    for (int _t = 0; _t < 2; ++_t) {
        vec.clear();
        vec.push_back(std::make_pair(0, -1));
        dfs(s, -1);

        int p = poisk(total, B);
        s = res[_t] = vec[p].first;
    }

    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