Submission #1285233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285233		mariaclara	Highway Tolls (IOI18_highway)	C++17	51 / 100	129 ms	12768 KiB

highway

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int C = (1<<16) - 10; 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int M;
ll D;
vector<vector<pii>> edges;
vi dist, pai;

pair<vi,vi> bfs(int raiz) {
    int n = sz(edges);

    dist.clear(); dist.resize(n, n+1);
    pai.clear(); pai.resize(n);

    queue<int> fila;
    fila.push(raiz);
    dist[raiz] = 0;

    while(!fila.empty()) {
        int no = fila.front();
        fila.pop();

        for(auto [viz, ind] : edges[no]) {
            if(dist[viz] <= dist[no] + 1) continue;
            dist[viz] = dist[no] + 1;
            pai[viz] = ind;
            fila.push(viz);
        }
    }

    return {dist, pai};
}

int busca(vi no) {
    sort(all(no), [](int a, int b){
        if(dist[a] == dist[b]) return a < b;
        return dist[a] > dist[b];
    });

    vi query(M);

    int l = 0, r = sz(no)-1;

    while(l < r) {
        int mid = (l+r)/2;

        fill(all(query), 0);
        for(int i = 0; i <= mid; i++) query[pai[no[i]]] = 1;

        if(ask(query) > D) r = mid;
        else l = mid+1;
    }

    return no[r];
}

void find_pair(int N, vi U, vi V, int A, int B) {
    M = sz(U);

    vi query(M);
    D = ask(query);

    int l = 0, r = M-1;
    while(l < r) {
        int mid = (l+r+1)/2;

        fill(all(query), 0);
        for(int i = 0; i < mid; i++) query[i] = 1;
                
        if(ask(query) > D) r = mid-1;
        else l = mid;
    }
    
    edges.resize(N);
    for(int i = 0; i < M; i++) {
        edges[U[i]].pb({V[i], i});
        edges[V[i]].pb({U[i], i});
    }

    int rs = U[l], rt = V[l];
    auto [ds,ps] = bfs(rs);
    auto [dt,pt] = bfs(rt);
    ps[rs] = pt[rt] = l;

    vi S, T;

    for(int i = 0; i < N; i++) {
        if(ds[i] < dt[i]) S.pb(i), dist[i] = ds[i], pai[i] = ps[i];
        if(dt[i] < ds[i]) T.pb(i), dist[i] = dt[i], pai[i] = pt[i];
    }

    answer(busca(S), busca(T));
}

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