Submission #463708

#	Time	Username	Problem	Language	Result	Execution time	Memory
463708		oscar1f	Highway Tolls (IOI18_highway)	C++17	12 / 100	165 ms	9876 KiB

highway

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

//#define int long long

const int MAX_SOM=90*1000;
int nbSom,bas,haut,nbAre,distTotal,petit,grand,mid,rep;
vector<int> deb,fin,quest;
vector<pair<int,int>> bonneDist;
vector<pair<int,int>> adja[MAX_SOM];
int dv[MAX_SOM];

void DFS(int pos,int dist,int anc) {
  if (dv[pos]==0) {
    dv[pos]=1;
    if (dist*bas==distTotal) {
      bonneDist.push_back(make_pair(pos,anc));
    }
    for (int i=0;i<adja[pos].size();i++) {
      DFS(adja[pos][i].first,dist+1,adja[pos][i].second);
    }
  }
}

void find_pair(int N,vector<int> U,vector<int> V,int A,int B) {
  nbAre=U.size();
  nbSom=N;
  deb=U;
  fin=V;
  bas=A;
  haut=B;
  for (int i=0;i<nbAre;i++) {
    quest.push_back(0);
  }
  distTotal=ask(quest);
  for (int i=0;i<nbAre;i++) {
    adja[deb[i]].push_back(make_pair(fin[i],i));
    adja[fin[i]].push_back(make_pair(deb[i],i));
  }
  DFS(0,0,0);
  petit=0;
  grand=bonneDist.size()-1;
  while(petit!=grand) {
    mid=(petit+grand)/2;
    for (int i=petit;i<=mid;i++) {
      quest[bonneDist[i].second]=1;
    }
    rep=ask(quest);
    for (int i=petit;i<=mid;i++) {
      quest[bonneDist[i].second]=0;
    }
    if (rep>distTotal) {
      grand=mid;
    }
    else {
      petit=mid+1;
    }
  }
  answer(0,bonneDist[petit].first);
}

Compilation message (stderr)

highway.cpp: In function 'void DFS(int, int, int)':
highway.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i=0;i<adja[pos].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