Submission #463707

#	Time	Username	Problem	Language	Result	Execution time	Memory
463707		oscar1f	Highway Tolls (IOI18_highway)	C++17	5 / 100	15 ms	3636 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;
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);
  //cout<<distTotal<<endl;
  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);
  for (int i=0;i<bonneDist.size();i++) {
    quest[bonneDist[i].second]=1;
    //cout<<bonneDist[i].first<<" "<<bonneDist[i].second<<" "<<ask(quest)<<endl;
    if (ask(quest)>distTotal) {
      answer(0,bonneDist[i].first);
    }
    quest[bonneDist[i].second]=0;
  }
}

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

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