Submission #1219082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219082		JooDdae	Highway Tolls (IOI18_highway)	C++20	51 / 100	337 ms	26500 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();
    vector<vector<array<int, 2>>> v(N);
    for(int i=0;i<M;i++) {
        v[U[i]].push_back({V[i], i});
        v[V[i]].push_back({U[i], i});
    }

    auto query = [&](vector<vector<int>> L) {
        vector<int> w(M, 0);
        for(auto v : L) for(auto x : v) w[x] = 1;
        return ask(w);
    };

    auto bfs = [&](int s) -> pair<vector<int>, vector<vector<int>>> {
        vector<int> d(N, -1);
        vector<vector<int>> p(N);

        queue<int> q;
        q.push(s), d[s] = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(auto [x, id] : v[u]) {
                if(d[x] == -1) q.push(x), d[x] = d[u]+1;
                if(d[x] == d[u]+1) p[x].push_back(id);
            }
        }

        return {d, p};
    };

    ll D = query({});

    auto find_deepest = [&](int s, vector<int> e) -> array<int, 2> {
        auto [d, p] = bfs(s);

        vector<array<int, 2>> L;
        for(auto x : e) L.push_back({d[x], x});
        sort(L.rbegin(), L.rend());

        vector<vector<int>> P;
        for(auto [x, y] : L) P.push_back(p[y]);
        
        int l = 1, r = (int)L.size()-1;
        while(l <= r) {
            int mid = (l+r) >> 1;
            if(query(vector<vector<int>>(P.begin(), P.begin()+mid)) == D) l = mid+1;
            else r = mid-1;
        }

        return {L[r][1], P[r].empty() ? -1 : P[r][0]};
    };

    vector<int> E(N, 0); iota(E.begin(), E.end(), 0);
    auto [S, P] = find_deepest(0, E);
    int T = V[P] ^ U[P] ^ S;

    vector<int> d[2] = {bfs(S).first, bfs(T).first}, e[2];
    for(int i=0;i<N;i++) e[d[0][i] > d[1][i]].push_back(i);


    int ans[2] = {-1, -1};
    for(int i=0;i<2;i++) ans[i] = find_deepest(i?T:S, e[i])[0];

    answer(ans[0], ans[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