Submission #250328

#	Time	Username	Problem	Language	Result	Execution time	Memory
250328		Osama_Alkhodairy	Highway Tolls (IOI18_highway)	C++17	90 / 100	655 ms	12508 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, bool b){
    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);
        }
    }
    if(b){
        while(depth[nodes.back()] != dist){
            nodes.pop_back();
        }
    }
    reverse(nodes.begin(), nodes.end());
    if(b){
        while(depth[nodes.back()] != dist){
            nodes.pop_back();
        }
    }
    while(depth[nodes.back()] < dist / 2){
        nodes.pop_back();
    }
    int l = 0, r = (int)nodes.size() - 1;
    while(l <= r){
        int mid = (l + r) / 2;
        vector <int> check(m), vis(m);
        for(int i = 0 ; i <= mid ; i++){
            for(auto &j : g[nodes[i]]){
                if(vis[j.second]) continue;
                vis[j.second] = 1;
                check[j.second] = 1;
            }
        }
        if(ask(check) != light) r = mid - 1;
        else l = mid + 1;
    }
    return nodes[l];
}
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, 0);
    int t = find(s, 1);
    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