Submission #1017053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017053		Unforgettablepl	Highway Tolls (IOI18_highway)	C++17	90 / 100	153 ms	12744 KiB

highway

#include <bits/stdc++.h>
using namespace std;
 
#define all(x) x.begin(),x.end()
 
long long ask(const std::vector<int> &w);
void answer(int s, int t);
 
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    vector<vector<pair<int,int>>> adj(N);
    vector<int> baseask;
    int M = U.size();
    for(int i=0;i<U.size();i++){
        adj[U[i]].emplace_back(V[i],i);
        adj[V[i]].emplace_back(U[i],i);
    }
    auto base = ask(vector<int>(M));
    int pathver = 0;
    {
        auto check = [&](int x){
            vector<int> a(M);
            for(int i=0;i<x;i++)a[i]=1;
            return base==ask(a);
        };
        for(int jump = 65536;jump;jump/=2){
            if(pathver+jump>=M)continue;
            if(check(pathver+jump))pathver+=jump;
        }
        pathver = U[pathver];
    }
    vector<int> pedge(N);
    vector<int> depth(N);
    auto bfs = [&](int x){
        baseask = vector<int>(M);
        queue<tuple<int,int,int,int>> q;
        q.emplace(0,-1,x,-1);
        vector<bool> visited(N);
        while(!q.empty()){
            auto [dep,par,idx,actpar] = q.front();q.pop();
            if(visited[idx]){
                baseask[par]=1;
                continue;
            }
            visited[idx]=true;
            pedge[idx]=par;
            depth[idx]=dep;
            for(auto[v,i]:adj[idx])if(v!=actpar)q.emplace(dep+1,i,v,idx);
        }
    };
    bfs(pathver);
    auto basedep = base/((long long)A);
    // Calculate st
    vector<pair<int,int>> arr;
    for(int i=0;i<N;i++)arr.emplace_back(depth[i],i);
    sort(arr.rbegin(),arr.rend());
    auto check = [&](int x){
        vector<int> wt = baseask;
        for(int i=0;i<x;i++)wt[pedge[arr[i].second]]=1;
        return base==ask(wt);
    };
    int st = 0;
    for(int jump = 65536;jump;jump/=2){
        if(st+jump>=N)continue;
        if(check(st+jump))st+=jump;
    }
    st = arr[st].second;
    bfs(st);
    vector<int> sus;
    for(int i=0;i<N;i++)if(depth[i]==basedep)sus.emplace_back(i);
    while(sus.size()>1){
        int mid = (sus.size())/2;
        vector<int> left,right;
        for(int i=0;i<mid;i++)left.emplace_back(sus[i]);
        for(int i=mid;i<sus.size();i++)right.emplace_back(sus[i]);
        vector<int> w = baseask;
        for(int&i:left)w[pedge[i]]=1;
        auto ans = ask(w);
        if(ans!=base)sus=left;
        else sus=right;
    }
    answer(st, sus[0]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<U.size();i++){
      |                 ~^~~~~~~~~
highway.cpp:74:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(int i=mid;i<sus.size();i++)right.emplace_back(sus[i]);
      |                       ~^~~~~~~~~~~

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