Submission #1055494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055494		Ahmed57	Highway Tolls (IOI18_highway)	C++17	12 / 100	97 ms	13904 KiB

highway

#include "bits/stdc++.h"
#include "highway.h"
 
using namespace std;
#define int long long
pair<int,int> p[100001];
int dep[100001];
vector<pair<int,int>> adj[100001];
void dfs(int i){
    queue<int> q;
    q.push(0);
    dep[0] = 1;
    p[0] = {0,-1};
    while(!q.empty()){
        int f = q.front();q.pop();
        for(auto j:adj[f]){
            if(dep[j.first]==0){
                dep[j.first] = dep[f]+1;
                p[j.first] = {f,j.second};
                q.push(j.first);
            }
        }
    }
}
 
void find_pair(int32_t N, vector<int32_t> U, vector<int32_t> V, int32_t A, int32_t B){
    int m = U.size();
    int n = N;
    vector<int32_t> as(m,0);
    int len = ask(as);
    for(int i = 0;i<U.size();i++){
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }
    int l = 0 ,r = n-1 , ans = 0;
    while(l<=r){
        int mid = (l+r)/2;
        vector<int32_t> as(m,0);
        for(int i = mid+1;i<n;i++){
            for(auto j:adj[i]){
                as[j.second] = 1;
            }
        }
        if(ask(as)==len){
            ans = mid;
            r = mid-1;
        }else l = mid+1;
    }
    dfs(ans);
    vector<pair<int,int>> v;
    for(int i = 0;i<N;i++){
        v.push_back({dep[i],i});
    }
    sort(v.begin(),v.end());
    l = 1 , r = n-1 ;int ans2 = 0;
    while(l<=r){
        int mid = (l+r)/2;
        vector<int32_t> as(m,1);
        for(int i = 1;i<=mid;i++){
            as[p[v[i].second].second] =0 ;
        }
        if(ask(as)==len){
            ans2 = mid;
            r = mid-1;
        }else l = mid+1;
    }
    int a = v[ans2].second;
    l = 0 , r = ans2-1 ;
    int ans3 = 0;
    while(l<=r){
        int mid = (l+r)/2;
        vector<int32_t> as(m,1);
        for(int i = 1;i<=mid;i++){
            as[p[v[i].second].second] = 0;
        }
        int f = a;
        while(p[f].second!=-1){
            as[p[f].second] = 0;
            f = p[f].first;
        }
        if(ask(as)==len){
            ans3 = mid;
            r = mid-1;
        }else l = mid+1;
    }
    int b = v[ans3].second;
    answer(a,b);
}

Compilation message (stderr)

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

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