Submission #1017065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017065		Unforgettablepl	Highway Tolls (IOI18_highway)	C++17	51 / 100	108 ms	10728 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);
    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,1));
    int pathver = 0;
    int ue = 0;
    int ve = 0;
    {
        auto check = [&](int x){
            vector<int> a(M,1);
            for(int i=0;i<x;i++)a[i]=0;
            return base==ask(a);
        };
        for(int jump = 65536;jump;jump/=2){
            if(pathver+jump>=M)continue;
            if(check(pathver+jump))pathver+=jump;
        }
        ue = U[pathver];
        ve = V[pathver];
    }
    vector<int> pedge;
    vector<int> depth;
    auto bfs = [&](int x){
        depth = vector<int>(N);
        pedge = vector<int>(N);
        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])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);
        }
    };
    auto getsol = [&](vector<bool> activeidx){
        vector<pair<int,int>> arr;
        for(int i=0;i<N;i++)if(activeidx[i])arr.emplace_back(depth[i],i);
        sort(arr.rbegin(),arr.rend());
        auto check = [&](int x){
            vector<int> wt(M,1);
            for(int i=0;i<x;i++)wt[pedge[arr[i].second]]=0;
            return base==ask(wt);
        };
        int st = 0;
        for(int jump = 65536;jump;jump/=2){
            if(st+jump>=arr.size())continue;
            if(check(st+jump))st+=jump;
        }
        return arr[st].second;
    };
    vector<int> depthu,pedgeu,depthv,pedgev;
    bfs(ue);
    swap(depth,depthu);
    swap(pedge,pedgeu);
    bfs(ve);
    swap(depth,depthv);
    swap(pedge,pedgev);
    int a,b;
    vector<bool> activeu(N),activev(N);
    for(int i=0;i<N;i++){
        if(depthu[i]<depthv[i])activeu[i]=true;
        else if(depthu[i]>depthv[i])activev[i]=true;
    }
    swap(depth,depthu);
    swap(pedge,pedgeu);
    a = getsol(activeu);
    swap(depth,depthv);
    swap(pedge,pedgev);
    b = getsol(activev);
    answer(a,b);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<U.size();i++){
      |                 ~^~~~~~~~~
highway.cpp: In lambda function:
highway.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             if(st+jump>=arr.size())continue;
      |                ~~~~~~~^~~~~~~~~~~~

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