Submission #1216656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216656		the_coding_pooh	Highway Tolls (IOI18_highway)	C++20	69 / 100	1541 ms	39520 KiB

highway

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

using namespace std;

#define fs first
#define sc second

#define all(x) x.begin(), x.end()

int M;

const int SIZE = 9e4 + 4;

vector <int> graph[SIZE];

long long original_dist;

map <pair<int, int>, int> edge_id;

vector <pair<int, int>> always_blocked;

bool query_edges(vector <pair<int, int>> &edges){
    vector<int> w(M, 0);
    for(auto i:edges){
        w[edge_id[i]] = 1;
    }
    for(auto i:always_blocked){
        w[edge_id[i]] = 1;
    }
    return ask(w) != original_dist;
}

bitset <SIZE> been;

int order[SIZE];

vector <int> in_edge[SIZE];

int dist[SIZE];

int cnt;

void get_BFS_DAG(int nd){
    dist[nd] = 0;
    queue <int> q;
    q.push(nd);
    been[nd] = 1;
    while (!q.empty()){
        int i = q.front();
        q.pop();
        for (auto j : graph[i]){
            if (been[j]){
                if(dist[j] == dist[i] + 1)
                    in_edge[j].push_back(i);
                continue;
            }
            been[j] = 1;
            dist[j] = dist[i] + 1;
            in_edge[j].push_back(i);
            q.push(j);
        }
    }
    uwu;
}

void get_dfs_order(int nd){
    cnt++;
    order[cnt] = nd;
    been[nd] = 1;
    for (auto i : graph[nd]){
        if(been[i] || dist[i] != dist[nd] + 1){
            continue;
        }
        get_dfs_order(i);
    }
    return;
}

int find_BFS_DAG_stuff(int nd, int pa){
    been.reset();
    memset(dist, 0x3f, sizeof(dist));
    get_BFS_DAG(nd);
    been.reset();
    cnt = 0;
    get_dfs_order(nd);
    int ret = nd;
    for (int L = 1, R = cnt, M; L != R;){
        M = (L + R + 1) / 2;
        vector <pair<int, int>> block;
        for (int i = M; i <= cnt; i++){
            for(auto j:in_edge[order[i]]){
                block.push_back({order[i], j});
            }
        }
        if(query_edges(block)){
            L = M;
        }
        else{
            R = M - 1;
        }
        ret = order[L];
    }
    return ret;
}

pair <int, int> find_split_edge(int M, int N, vector <int> &U, vector <int> &V){
    int ret = 0;
    for (int l = 0, r = M - 1, m; l != r;){
        m = (l + r + 1) / 2;
        vector <pair<int, int>> block;
        for (int i = m; i < M; i++){
            block.push_back({U[i], V[i]});
        }
        if(query_edges(block)){
            l = m;
        }
        else{
            r = m - 1;
        }
        ret = l;
    }
    set <pair<int, int>> ab;
    for (int i = ret + 1; i < M; i++){
        ab.insert({U[i], V[i]});
        ab.insert({V[i], U[i]});
        always_blocked.push_back({U[i], V[i]});
    }
    for (int i = 0; i < N; i++){
        vector <int> ng;
        for(auto j:graph[i]){
            if(ab.count({i, j}))
                continue;
            ng.push_back(j);
        }
        graph[i] = ng;
    }
    return {U[ret], V[ret]};
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
    M = U.size();
    vector<int> w(M);
    for (int i = 0; i < M; ++i) {
        w[i] = 0;
    }
    original_dist = ask(w);
    for (int i = 0; i < M; i++){
        edge_id[{U[i], V[i]}] = i;
        edge_id[{V[i], U[i]}] = i;
        graph[U[i]].push_back(V[i]);
        graph[V[i]].push_back(U[i]);
    }
    pair<int, int> split = find_split_edge(M, N, U, V);
    // cout << split.fs << ' ' << split.sc << '\n';
    int s = find_BFS_DAG_stuff(split.fs, split.sc), t = find_BFS_DAG_stuff(split.sc, split.fs);
    // cout << s << ' ' << t << '\n';
    answer(s, t);
    uwu;
}

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