Submission #1150288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150288		Noname_1900	Race (IOI11_race)	C++20	21 / 100	3095 ms	12092 KiB

race

#include "race.h"
using namespace std;
#include <bits/stdc++.h>
const int NMAX = 200000;
#define int long long
vector<pair<int, int>> chemins[NMAX];
struct T {
  int longueur, noeud, nbAretesPrises;
  T(int _1, int _2, int _3)
  {
    longueur = _1; noeud = _2; nbAretesPrises = _3;
  }
  bool operator<(const T & other) const {
    return longueur > other.longueur;
  }
};
#undef int
int dejaVu[NMAX];
int best_path(int N, int K, int H[][2], int L[])
{
  #define int long long
  for(int iC = 0; iC < N-1; iC++)
  {
    int a = H[iC][0], b = H[iC][1], longueur = L[iC];
    chemins[a].push_back({b, longueur});
    chemins[b].push_back({a, longueur}); 
  }
  int meill = NMAX;
  for(int iNoeud = 0; iNoeud < N; iNoeud++)
  {
      priority_queue<T> plusCourtNoeud;
      plusCourtNoeud.push(T(0, iNoeud, 0));
      while(plusCourtNoeud.size())
      {
        auto cas = plusCourtNoeud.top();
        plusCourtNoeud.pop();
        if(dejaVu[cas.noeud] == iNoeud+1) continue;
        if(cas.longueur > K)  break;
        if(cas.longueur == K)
        {
          meill = min(meill, cas.nbAretesPrises);
          continue;
        }  
        dejaVu[cas.noeud] = iNoeud+1;
        for(auto pro : chemins[cas.noeud])
        {
          plusCourtNoeud.push(T(cas.longueur+pro.second, pro.first, cas.nbAretesPrises+1));
        }

      
      }

  }
  if(meill == NMAX) meill = -1;
  return meill;
}

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