Submission #848720

#	Time	Username	Problem	Language	Result	Execution time	Memory
848720		12345678	Race (IOI11_race)	C++17	100 / 100	311 ms	71344 KiB

race

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

using namespace std;

const int nx=2e5+5, kx=1e6+5;
int n, k, sz[nx], ans=INT_MAX, dp[kx];
bool used[nx];
vector<pair<int, int>> d[nx], res[nx];


int dfssz(int u, int p)
{
  sz[u]=1;
  for (auto [v, w]:d[u]) if (v!=p&&!used[v]) sz[u]+=dfssz(v, u);
  return sz[u];
}

int findcentroid(int u, int p, int rtsz)
{
  for (auto [v, w]:d[u]) if (v!=p&&!used[v]&&2*sz[v]>rtsz) return findcentroid(v, u, rtsz);
  return u; 
}

void dfs(int u, vector<pair<int, int>> &vec, int ds, int len, int p)
{
  if (ds>k) return;
  vec.push_back({ds, len});
  for (auto [v, w]:d[u]) if (v!=p&&!used[v]) dfs(v, vec, ds+w, len+1, u);
}

void decom(int u)
{
  u=findcentroid(u, -1, dfssz(u, -1));
  used[u]=1;
  for (auto [v, w]:d[u]) 
  {
    if (used[v]) continue;
    dfs(v, res[v], w, 1, u);
    for (auto [ds, len]:res[v]) ans=min(ans, len+dp[k-ds]);
    for (auto [ds, len]:res[v]) dp[ds]=min(dp[ds], len);
  }
  for (auto [v, w]:d[u])
  {
    if (used[v]) continue;
    for (auto [ds, len]:res[v]) dp[ds]=1e9;
    res[v].clear();
  }
  for (auto [v, w]:d[u]) if (!used[v]) decom(v);
}

int best_path(int N, int K, int H[][2], int L[])
{
  n=N; k=K;
  dp[0]=0;
  for (int i=1; i<=k; i++) dp[i]=1e9;
  for (int i=0; i<n-1; i++) d[H[i][0]].push_back({H[i][1], L[i]}), d[H[i][1]].push_back({H[i][0], L[i]});
  decom(0);
  return ans>=1e9?-1:ans;
}

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