Submission #339038

#	Time	Username	Problem	Language	Result	Execution time	Memory
339038		bigDuck	Race (IOI11_race)	C++14	21 / 100	32 ms	4332 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount

int n, k;
vector<pii> g[1010];
bool v[1010];


int dfs(int s, int l, int h){
int res=1e9;
    if(l>k){
        return res;
    }
    if(l==k){
        return h;
    }
    v[s]=true;
    for(pii pr:g[s]){
        int u=pr.ft, d=pr.sc;
        if(!v[u]){
            res=min(dfs(u, l+d, h+1), res);
        }
    }
    v[s]=false;
    return res;
}



int best_path(int N, int K, int H[][2], int L[])
{
  n=N; k=K;
  int res=1e9;
  for(int i=0; i<n; i++){
    int u=H[i][0]+1, v=H[i][1]+1, d=L[i];
    g[u].pb({v, d}); g[v].pb({u, d});
  }
  for(int i=1; i<=n;i++){
    res=min(res, dfs(i, 0, 1));
  }
  if(res==(1e9)){
    return -1;
  }
  return res-1;
}

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