Submission #1260700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260700		comgaTramAnh	Race (IOI11_race)	C++20	100 / 100	306 ms	34492 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<pair<int,int>> adj[200005];
int minDist[1000005];
int sizeSubTree[200005];
bool used[200005];
int ans;
vector<int> touched;

void dfsSize(int u, int p)
{
  sizeSubTree[u] = 1;
  for (int i = 0; i < (int) adj[u].size(); i++)
  {
    int v = adj[u][i].first;
    if (v == p || used[v])
    {
      continue;
    }
    dfsSize(v, u);
    sizeSubTree[u] += sizeSubTree[v];
  }
}

int findCentroid(int u, int p, int total)
{
  for (int i = 0; i < (int) adj[u].size(); i++)
  {
    int v = adj[u][i].first;
    if (v == p || used[v])
    {
      continue;
    }
    if (2 * sizeSubTree[v] > total)
    {
      return findCentroid(v, u, total);
    }
  }
  return u;
}

void dfs(int u, int p, int edges, int dist, bool writeMode)
{
  if (dist > k)
  {
    return;
  }
  if (!writeMode)
  {
    int need = k - dist;
    if (need >= 0 && minDist[need] < n + 5)
    {
      ans = min(ans, edges + minDist[need]);
    }
  }
  else
  {
    if (minDist[dist] > edges)
    {
      if (minDist[dist] == n + 5)
      {
        touched.push_back(dist);
      }
      minDist[dist] = edges;
    }
  }
  for (int i = 0; i < (int) adj[u].size(); i++)
  {
    int v = adj[u][i].first;
    int w = adj[u][i].second;
    if (v == p || used[v])
    {
      continue;
    }
    dfs(v, u, edges + 1, dist + w, writeMode);
  }
}

void decompose(int u)
{
  dfsSize(u, -1);
  int c = findCentroid(u, -1, sizeSubTree[u]);
  used[c] = true;

  minDist[0] = 0;
  touched.push_back(0);

  for (int i = 0; i < (int) adj[c].size(); i++)
  {
    int v = adj[c][i].first;
    int w = adj[c][i].second;
    if (used[v])
    {
      continue;
    }
    dfs(v, c, 1, w, false);
    dfs(v, c, 1, w, true);
  }

  for (int d : touched)
  {
    minDist[d] = n + 5;
  }
  touched.clear();

  for (int i = 0; i < (int) adj[c].size(); i++)
  {
    int v = adj[c][i].first;
    if (!used[v])
    {
      decompose(v);
    }
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  n = N;
  k = K;
  for (int i = 0; i < n; i++)
  {
    adj[i].clear();
    used[i] = false;
  }
  for (int i = 0; i <= k; i++)
  {
    minDist[i] = n + 5;
  }
  for (int i = 0; i < n - 1; i++)
  {
    int u = H[i][0];
    int v = H[i][1];
    int w = L[i];
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  ans = n + 5;
  decompose(0);
  return (ans == n + 5 ? -1 : ans);
}

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