Submission #250310

#	Time	Username	Problem	Language	Result	Execution time	Memory
250310		Osama_Alkhodairy	Highway Tolls (IOI18_highway)	C++17	90 / 100	411 ms	12628 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long

int n, m;
vector <pair <int, int> > es, g[90001];
ll light;
int dist;

int find(int root){
    vector <bool> vis(n);
    queue <int> ready;
    vector <int> depth(n);
    ready.push(root);
    vector <int> nodes;
    vis[root] = 1;
    while(ready.size()){
        int node = ready.front();
        ready.pop();
        nodes.push_back(node);
        for(auto &i : g[node]){
            if(vis[i.first]) continue;
            vis[i.first] = 1;
            depth[i.first] = depth[node] + 1;
            ready.push(i.first);
        }
    }
    reverse(nodes.begin(), nodes.end());
    vis.assign(m, 0);
    vector <int> edges;
    for(auto &i : nodes){
        for(auto &j : g[i]){
            if(vis[j.second]) continue;
            vis[j.second] = 1;
            edges.push_back(j.second);
        }
    }
    int l = 0, r = m - 1;
    while(max(depth[es[edges[l]].first], depth[es[edges[l]].second]) < dist / 2){
        l++;
    }
    while(l <= r){
        int mid = (l + r) / 2;
        vector <int> check(m);
        for(int i = 0 ; i <= mid ; i++){
            check[edges[i]] = 1;
        }
        if(ask(check) != light) r = mid - 1;
        else l = mid + 1;
    }
    auto edge = es[edges[l]];
    if(depth[edge.first] > depth[edge.second]) return edge.first;
    return edge.second;
}
void find_pair(int N, std::vector<int> u, std::vector<int> v, int a, int b) {
    n = N;
    m = u.size();
    for(int i = 0 ; i < m ; i++){
        g[u[i]].push_back(make_pair(v[i], i));
        g[v[i]].push_back(make_pair(u[i], i));
        es.push_back(make_pair(u[i], v[i]));
    }
    light = ask(vector <int>(m, 0));
    dist = light / a;
    int l = 0, r = m - 1;
    while(l <= r){
        int mid = (l + r) / 2;
        vector <int> check(m);
        for(int i = 0 ; i <= mid ; i++){
            check[i] = 1;
        }
        if(ask(check) != light) r = mid - 1;
        else l = mid + 1;
    }
    int root = es[l].first;
    int s = find(root);
    int t = find(s);
    answer(s, t);
}

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