Submission #426055

#	Time	Username	Problem	Language	Result	Execution time	Memory
426055		oscar1f	Race (IOI11_race)	C++17	21 / 100	79 ms	8216 KiB

race

#include<bits/stdc++.h>
//#include <cstdio>
//#include <cstdlib>
using namespace std; 


/*#define MAX_N 500000

int N, K;
int H[MAX_N][2];
int L[MAX_N];
int solution;

inline 
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(2==scanf("%d %d",&N,&K));
  for(i=0; i<N-1; i++)
    my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  my_assert(1==scanf("%d",&solution));
}*/

const int TAILLE_MAX=1000,INFINI=1000*1000*1000;
int deb;
vector<pair<int,int>> adja[TAILLE_MAX];
int dist[TAILLE_MAX][TAILLE_MAX][2];

void DFS(int pos,int distKm,int distArete) {
  if (dist[deb][pos][0]==-1) {
    dist[deb][pos][0]=distKm;
    dist[deb][pos][1]=distArete;
    for (int ivois=0;ivois<adja[pos].size();ivois++) {
      DFS(adja[pos][ivois].first,distKm+adja[pos][ivois].second,distArete+1);
    }
  }
}

int best_path(int nbSom, int taille, int aretes[][2], int longueurs[]) {
  int record=INFINI;
  for (int i=0;i<nbSom-1;i++) {
    adja[aretes[i][0]].push_back(make_pair(aretes[i][1],longueurs[i]));
    adja[aretes[i][1]].push_back(make_pair(aretes[i][0],longueurs[i]));
  }
  for (int i=0;i<nbSom;i++) {
    for (int j=0;j<nbSom;j++) {
      dist[i][j][0]=-1;
    }
  }
  for (int i=0;i<nbSom;i++) {
    deb=i;
    DFS(i,0,0);
  }
  for (int i=0;i<nbSom;i++) {
    for (int j=0;j<nbSom;j++) {
      if (dist[i][j][0]==taille) {
        record=min(record,dist[i][j][1]);
      }
    }
  }
  if (record==INFINI) {
    record=-1;
  }
  return record;
}
/*
int main()
{
  int ans;
  read_input();
  ans = best_path(N,K,H,L);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}
*/

Compilation message (stderr)

race.cpp: In function 'void DFS(int, int, int)':
race.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int ivois=0;ivois<adja[pos].size();ivois++) {
      |                      ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57