Submission #971976

#	Time	Username	Problem	Language	Result	Execution time	Memory
971976		onlk97	Highway Tolls (IOI18_highway)	C++14	51 / 100	238 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector <pair <int,int> > g[100010];
int pa[100010],dep[100010];
vector <int> is;
void dfs(int cur,int prv,bool r){
    if (r) dep[cur]=0;
    else dep[cur]=dep[prv]+1;
    for (auto i:g[cur]){
        if (i.first!=prv){
            pa[i.first]=i.second;
            is.push_back(i.second);
            dfs(i.first,cur,0);
        }
    }
}
void find_pair(int n,vector <int> u,vector <int> v,int a,int b){
    int m=u.size();
    vector <int> tt(m,0);
    long long dist0=ask(tt);
    int l=0,r=m-1;
    while (l<r){
        int mid=(l+r)/2;
        vector <int> tp(m,0);
        for (int i=l; i<=mid; i++) tp[i]=1;
        long long dist1=ask(tp);
        if (dist0!=dist1) r=mid;
        else l=mid+1;
    }
    for (int i=0; i<m; i++){
        g[u[i]].push_back({v[i],i});
        g[v[i]].push_back({u[i],i});
    }
    is.clear();
    for (int i=0; i<n; i++) dep[i]=-1;
    dfs(u[l],v[l],1);
    vector <int> tp(m,0);
    for (int i:is) tp[i]=1;
    long long dist1=ask(tp);
    long long d=(dist1-dist0)/(1LL*(b-a));
    vector <int> cand;
    for (int i=0; i<n; i++){
        if (dep[i]==d) cand.push_back(i); 
    }
    while (cand.size()>1){
        for (int i=0; i<m; i++) tp[i]=0;
        for (int i=0; i<(cand.size()+1)/2; i++) tp[pa[cand[i]]]=1;
        dist1=ask(tp);
        vector <int> nw;
        if (dist0!=dist1){
            for (int i=0; i<(cand.size()+1)/2; i++) nw.push_back(cand[i]); 
        } else {
            for (int i=(cand.size()+1)/2; i<cand.size(); i++) nw.push_back(cand[i]);
        }
        cand=nw;
    }
    int ans=cand[0];
    is.clear();
    for (int i=0; i<n; i++) dep[i]=-1;
    dfs(v[l],u[l],1);
    for (int i=0; i<m; i++) tp[i]=0;
    for (int i:is) tp[i]=1;
    dist1=ask(tp);
    d=(dist1-dist0)/(1LL*(b-a));
    cand.clear();
    for (int i=0; i<n; i++){
        if (dep[i]==d) cand.push_back(i); 
    }
    while (cand.size()>1){
        for (int i=0; i<m; i++) tp[i]=0;
        for (int i=0; i<(cand.size()+1)/2; i++) tp[pa[cand[i]]]=1;
        dist1=ask(tp);
        vector <int> nw;
        if (dist0!=dist1){
            for (int i=0; i<(cand.size()+1)/2; i++) nw.push_back(cand[i]); 
        } else {
            for (int i=(cand.size()+1)/2; i<cand.size(); i++) nw.push_back(cand[i]);
        }
        cand=nw;
    }
    answer(ans,cand[0]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int i=0; i<(cand.size()+1)/2; i++) tp[pa[cand[i]]]=1;
      |                       ~^~~~~~~~~~~~~~~~~~
highway.cpp:52:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for (int i=0; i<(cand.size()+1)/2; i++) nw.push_back(cand[i]);
      |                           ~^~~~~~~~~~~~~~~~~~
highway.cpp:54:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for (int i=(cand.size()+1)/2; i<cand.size(); i++) nw.push_back(cand[i]);
      |                                           ~^~~~~~~~~~~~
highway.cpp:72:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int i=0; i<(cand.size()+1)/2; i++) tp[pa[cand[i]]]=1;
      |                       ~^~~~~~~~~~~~~~~~~~
highway.cpp:76:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for (int i=0; i<(cand.size()+1)/2; i++) nw.push_back(cand[i]);
      |                           ~^~~~~~~~~~~~~~~~~~
highway.cpp:78:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             for (int i=(cand.size()+1)/2; i<cand.size(); i++) nw.push_back(cand[i]);
      |                                           ~^~~~~~~~~~~~

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