Submission #406063

#	Time	Username	Problem	Language	Result	Execution time	Memory
406063		urd05	Highway Tolls (IOI18_highway)	C++14	51 / 100	200 ms	15136 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

int ind[100000];
int pos[100000];
typedef pair<int,int> P;
vector<P> adj[90000];
int cnt=1;

void dfs(int v,int prev) {
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i].first;
        if (nt==prev)
            continue;
        pos[adj[v][i].second]=nt;
        ind[cnt++]=adj[v][i].second;
        dfs(nt,v);
    }
}

void find_pair(int n,vector<int> u,vector<int> v,int a,int b) {
    int m=u.size();
    for(int i=0;i<u.size();i++) {
      adj[u[i]].push_back(P(v[i],i));
      adj[v[i]].push_back(P(u[i],i));
    }
    dfs(0,-1);
    vector<int> vec(m);
    int l=ask(vec)/a;
    int lo=0; //impossible
    int hi=n-1; //possible
    while (lo+1<hi) {
        int mid=(lo+hi)/2;
        for(int i=0;i<m;i++) {
            vec[i]=0;
        }
        for(int i=1;i<=mid;i++) {
            vec[ind[i]]=1;
        }
        if (ask(vec)==1LL*l*b) {
            hi=mid;
        }
        else {
            lo=mid;
        }
    }
    int v1=pos[ind[hi]];
    cnt=1;
    dfs(v1,-1);
    for(int i=0;i<m;i++) {
        vec[i]=0;
    }
    lo=0; //impossible
    hi=n-1; //possible
    while (lo+1<hi) {
        int mid=(lo+hi)/2;
        for(int i=0;i<m;i++) {
            vec[i]=0;
        }
        for(int i=1;i<=mid;i++) {
            vec[ind[i]]=1;
        }
        if (ask(vec)==1LL*l*b) {
            hi=mid;
        }
        else {
            lo=mid;
        }
    }
    int v2=pos[ind[hi]];
    answer(v1,v2);
}

Compilation message (stderr)

highway.cpp: In function 'void dfs(int, int)':
highway.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<u.size();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