Submission #821836

#	Time	Username	Problem	Language	Result	Execution time	Memory
821836		nemethm	Race (IOI11_race)	C++17	21 / 100	300 ms	246544 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long int;

vector<pair<int,ll>> g[200100];

int level[1001], dist[1001];

int k, ans = -1;

int minl[200100][110] = {0};

void dfs(int node, int prev = -1){
  if(dist[node] == k){
    ans = ans == -1 ? level[node] : min(ans, level[node]);
  }
  for(auto i : g[node]){
    if(i.first != prev){
      level[i.first] = level[node] + 1;
      dist[i.first] = dist[node] + i.second;
      dfs(i.first, node);
    }
  }
}

void dfs2(int node, int prev = -1){
  for(auto i : g[node]){
    if(i.first != prev){
      dfs2(i.first, node);
      vector<int> temp(k + 1);
      temp[i.second] = 1;
      for(int j = 1; j + i.second <= k; ++j){
        if(minl[i.first][j] == 0) continue;
        temp[j + i.second] = minl[i.first][j] + 1;
      }
      for(int j = 1; j < k; ++j){
        if(temp[j] > 0 && minl[node][k - j] > 0){
          if(ans == -1){
            ans = temp[j] + minl[node][k - j];
          }
          else{
            ans = min(ans, temp[j] + minl[node][k - j]);
          }
        }
      }
      if(temp[k] > 0){
        ans = ans == -1 ? temp[k] : min(ans, temp[k]);
      }
      minl[node][i.second] = 1;
      for(int j = 1; j + i.second <= k; ++j){
        if(minl[i.first][j] == 0) continue;
        if(minl[node][j + i.second] == 0){
          minl[node][j + i.second] = minl[i.first][j] + 1;
        }
        else{
          minl[node][j + i.second] = min(minl[i.first][j] + 1, minl[node][j + i.second]);
        }
      }
    }
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  k = K;
  for(int i = 0; i < N - 1; ++i){
    g[H[i][0]].push_back({H[i][1], L[i]});
    g[H[i][1]].push_back({H[i][0], L[i]});
  }
  if(N <= 1000){
    for(int i = 0; i < N; ++i){
      fill(level, level + N, 0);
      fill(dist, dist + N, 0);
      dfs(i);
    }
  }
  else{
    dfs2(0);
  }
  return ans;
}

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