Submission #818425

#	Time	Username	Problem	Language	Result	Execution time	Memory
818425		Jarif_Rahman	Highway Tolls (IOI18_highway)	C++17	51 / 100	189 ms	12536 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
 
int n, m;
ll A, B;
vector<vector<pair<int, int>>> graph;
 
void find_pair(int _n, vector<int> U, vector<int> V, int _A, int _B){
    swap(n, _n);
    m = U.size();
    A = _A, B = _B;
    graph.resize(n);
 
    for(int i = 0; i < m; i++){
        graph[U[i]].pb({V[i], i});
        graph[V[i]].pb({U[i], i});
    }
 
    ll def = ask(vector<int>(m, 0));
 
    int a = 0, b = m-1;
    while(a < b){
        int md = (a+b)/2;
        vector<int> w(m, 0);
        for(int i = 0; i <= md; i++) w[i] = 1;
        ll x = ask(w);
        if(x > def) b = md;
        else a = md+1;
    }
 
    int u = U[a], v = V[a];

    vector<int> disu(n, -1);
    queue<int> Q;
    disu[u] = 0;
    Q.push(u);
    vector<int> pu(n, -1), wu(m, 1);
    while(!Q.empty()){
        int nd = Q.front(); Q.pop();
        for(auto [x, i]: graph[nd]) if(disu[x] == -1){
            disu[x] = disu[nd]+1;
            pu[x] = i;
            wu[i] = 0;
            Q.push(x);
        }
    }

    vector<int> disv(n, -1);
    disv[v] = 0;
    Q.push(v);
    vector<int> pv(n, -1), wv(m, 1);
    while(!Q.empty()){
        int nd = Q.front(); Q.pop();
        for(auto [x, i]: graph[nd]) if(disv[x] == -1){
            disv[x] = disv[nd]+1;
            pv[x] = i;
            wv[i] = 0;
            Q.push(x);
        }
    }

    vector<int> unodes, vnodes;
    for(int i = 0; i < n; i++){
        if(disu[i] == disv[i]) continue;
        if(disu[i] < disv[i]) unodes.pb(i);
        else vnodes.pb(i);
    }

    sort(unodes.begin(), unodes.end(), [&](int x, int y){
        return disu[x] > disu[y];
    });
    sort(vnodes.begin(), vnodes.end(), [&](int x, int y){
        return disv[x] > disv[y];
    });

    int s, t;

    a = 0, b = int(unodes.size())-1;
    while(a < b){
        int md = (a+b)/2;
        vector<int> w = wu;
        for(int i = 0; i <= md; i++) if(pu[unodes[i]] != -1) w[pu[unodes[i]]] = 1;
        ll x = ask(w);
        if(x > def) b = md;
        else a = md+1;
    }
    s = unodes[a];

    a = 0, b = int(vnodes.size())-1;
    while(a < b){
        int md = (a+b)/2;
        vector<int> w = wv;
        for(int i = 0; i <= md; i++) if(pv[vnodes[i]] != -1) w[pv[vnodes[i]]] = 1;
        ll x = ask(w);
        if(x > def) b = md;
        else a = md+1;
    }
    t = vnodes[a];

    answer(s, 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