Submission #1199206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199206		ach00	Highway Tolls (IOI18_highway)	C++20	51 / 100	137 ms	11320 KiB

highway

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

vector<vector<pair<ll,ll>>> adj;
ll m;
ll n;
vector<int> _U, _V;
ll cw = -1;
ll len = -1;

vector<ll> dists(int i) {
    vector<ll> dist(n, -1);
    queue<int> q;
    q.push(i);
    dist[i] = 0;
    while(!q.empty()) {
        int v = q.front(); q.pop();
        for(auto &e : adj[v]) {
            int u = e.first;
            if(dist[u] != -1) continue;
            dist[u] = dist[v] + 1;
            q.push(u);
        }
    }
    return dist;
}

pair<int,int> fle(int start, int banned) {
    vector<pair<int,int>> S;
    queue<int> q;
    vector<int> dist(n, -1);
    q.push(start);
    dist[start] = 0;
    while(!q.empty()) {
        int v = q.front(); q.pop();
        int d = dist[v];
        for(auto &e : adj[v]) {
            int eid = e.second;
            int u = e.first;
            if(u == banned || dist[u] != -1) continue;
            S.push_back({d+1, eid});
            dist[u] = d + 1;
            q.push(u);
        }
    }
    sort(S.rbegin(), S.rend());
    vector<int> asdf(m, 0);
    int sz = S.size();
    for(int i = 0; i < sz; i++) {
        asdf[S[i].second] = 1;
    }
    if(ask(asdf) == cw) return {start,start};
    int lo = 0;
    int hi = sz-1;
    while(hi - lo > 2) {
        int p = (hi+lo)/2;
        vector<int> Q(m,0);
        for(int j = 0; j <= p; j++) {
            Q[S[j].second] = 1;
        }
        if(ask(Q) == cw) {
            lo = p+1;
        } else {
            hi = p;
        }
    }
    int EDGE = -1;
    for(int y = lo; y <= hi; y++) {
        vector<int> Q(m,0);
        for(int j = 0; j <= y; j++) {
            Q[S[j].second] = 1;
        }
        if(ask(Q) > cw) {
            EDGE = S[y].second;
            break;
        }
    }
    return {_U[EDGE], _V[EDGE]};
}

int eor() {
    int lo = 0;
    int hi = m-1;
    while(hi - lo > 2) {
        int p = (hi+lo)/2;
        vector<int> Q(m, 0);
        for(int j = 0; j <= p; j++) {
            Q[j] = 1;
        }
        if(ask(Q) > cw) {
            hi = p;
        } else {
            lo = p+1;
        }
    }
    for(int y = lo; y <= hi; y++) {
        vector<int> Q(m, 0);
        for(int j = 0; j <= y; j++) Q[j] = 1;
        if(ask(Q) > cw) return y;
    }
}

ll simple() {
    vector<int> Q(m, 0);
    return ask(Q);
}


void find_pair(int N, vector<int> U, vector<int> V, int a, int b) {
    n = N;
    m = U.size();
    _U = U;
    _V = V;
    adj.resize(N);
    for(int i = 0; i < m; i++) {
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }
    cw = simple();
    len = cw/(static_cast<ll>(a));
    int seid = eor();
    int u = U[seid];
    int v = V[seid];
    pair<int,int> ss = fle(u,v);
    pair<int,int> tt = fle(v,u);
    vector<ll> s1d = dists(ss.first);
    vector<ll> s2d = dists(ss.second);
    int s,t;
    if(s1d[tt.first] == len) {
        s = ss.first;
        t = tt.first; 
    } else if(s1d[tt.second] == len) {
        s = ss.first;
        t = tt.second;
    } else if(s2d[tt.first] == len) {
        s = ss.second;
        t = tt.first;
    } else {
        s = ss.second;
        t = tt.second;
    }
    answer(s,t);
}

Compilation message (stderr)

highway.cpp: In function 'int eor()':
highway.cpp:103:1: warning: control reaches end of non-void function [-Wreturn-type]
  103 | }
      | ^

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