Submission #445260

#	Time	Username	Problem	Language	Result	Execution time	Memory
445260		prvocislo	Race (IOI11_race)	C++17	100 / 100	1029 ms	41840 KiB

race

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

const int maxn = 2e5 + 5;
int n, k, ans = maxn;
vector<bool> alive(maxn, true);
vector<int> siz(maxn, 0);
vector<vector<pair<int, int> > > g(maxn);
void dfs_size(int u, int p = -1)
{
  siz[u] = 1;
  for (pair<int, int> i : g[u])
  {
    if (!alive[i.first] || i.first == p) continue;
    dfs_size(i.first, u);
    siz[u] += siz[i.first];
  }
}
int dfs_centroid(int u, int s, int p = -1)
{
  for (const pair<int, int> &i : g[u])
  {
    if (!alive[i.first] || i.first == p) continue;
    if (siz[i.first] > s/2) return dfs_centroid(i.first, s, u);
  }
  return u;
}
void dfs_dist(int u, vector<pair<int, int> > &v, int depth = 0, int dist = 0, int p = -1)
{
  if (dist == k) return (void)(ans = min(ans, depth));
  if (dist > k) return;
  v.push_back({dist, depth});
  for (pair<int, int> i : g[u])
  {
    if (!alive[i.first] || i.first == p) continue;
    dfs_dist(i.first, v, depth+1, dist+i.second, u);
  }
}
void centroid_decomp(int r)
{
  dfs_size(r);
  int u = dfs_centroid(r, siz[r]);
  map<int, int> m;
  alive[u] = false;
  for (const pair<int, int> &i : g[u])
  {
    if (!alive[i.first]) continue;
    centroid_decomp(i.first);
    vector<pair<int, int> > v;
    dfs_dist(i.first, v, 1, i.second, u);
    for (const pair<int, int> &j : v) 
    {
      //cout << m.count(k-j.first) << " " << m[k-j.first] << "\n";
      if (m.count(k-j.first)) 
        ans = min(ans, j.second+m[k-j.first]);
    }
    for (const pair<int, int> &j : v)
      if (!m.count(j.first))
        m[j.first] = j.second;
      else
        m[j.first] = min(m[j.first], j.second);
    //cout << "\n" << u << "\n";
    //for (pair<int, int> j : m) cout << j.first << " " << j.second << "\n";
  }
  alive[u] = true;
}
int best_path(int N, int K, int e[][2], int l[])
{
  n = N, k = K;
  for (int i = 0; i < n-1; i++)
  {
    g[e[i][0]].push_back({e[i][1], l[i]});
    g[e[i][1]].push_back({e[i][0], l[i]});
  }
  centroid_decomp(0);
  return ans == maxn ? -1 : ans;
}

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