Submission #254249

#	Time	Username	Problem	Language	Result	Execution time	Memory
254249		StevenH	Race (IOI11_race)	C++14	21 / 100	3073 ms	20604 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxk = 1e6 + 5;
const int maxn = 2e5 + 5;
const int inf = 1e9;
int dis[maxn], depth[maxn], tag[maxk], size[maxn];
int n, k, cur;
int dfn[maxn], last[maxn], rnk[maxn], cnt;
int ans;
vector<vector<pair<int, int> > > edge(maxn);
vector<int> pt(maxk);
inline void reset(int dist)
{
  if (tag[dist] != cur)
  {
    tag[dist] = cur;
    pt[dist] = dist ? inf : 0;
  }
  return;
}
void dfs1(int u, int f)
{
  cur++;
  for (int i = 0; i < edge[u].size(); i++)
  {
    int v = edge[u][i].first;
    if (f == v)
      continue;

    // cout << u << " " << f << endl;
    for (int j = dfn[v]; j <= last[v]; j++)
    {
      int dist = dis[rnk[j]] - dis[u];
      int dep = depth[rnk[j]] - depth[u];
      if (dist > k)
        continue;
      reset(k - dist);
      ans = min(ans, dep + pt[k - dist]);
    }
    for (int j = dfn[v]; j <= last[v]; j++)
    {
      // cout << rnk[j] << " ";
      int dist = dis[rnk[j]] - dis[u];
      int dep = depth[rnk[j]] - depth[u];
      if (dist > k)
        continue;
      reset(dist);
      pt[dist] = min(pt[dist], dep);
    }
  }
  // cout << "*" << endl;
  for (int i = 0; i < edge[u].size(); i++)
  {
    int v = edge[u][i].first;
    if (f == v)
      continue;
    dfs1(v, u);
  }
  return;
}
void init(int u, int f)
{
  // cout << u << " " << f << endl;
  dfn[u] = ++cnt;
  rnk[cnt] = u;
  for (int i = 0; i < edge[u].size(); i++)
  {
    int v = edge[u][i].first;
    int dist = edge[u][i].second;
    if (f == v)
      continue;
    dis[v] = dis[u] + dist;
    depth[v] = depth[u] + 1;
    init(v, u);
  }
  last[u] = cnt;
  return;
}
void calc_size(int u, int f)
{
  size[u] = 1;
  for (int i = 0; i < edge[u].size(); i++)
  {
    int v = edge[u][i].first;
    if (f == v)
      continue;
    calc_size(v, u);
    size[u] += size[v];
  }
}
int find_rt(int u, int f)
{
  // cerr << u << " " << f << endl;
  int mxsize = 0;
  for (int i = 0; i < edge[u].size(); i++)
  {
    int v = edge[u][i].first;
    if (f == v)
      continue;
    mxsize = max(mxsize, size[v]);
    int res = find_rt(v, u);
    if (res != -1)
      return res;
  }
  mxsize = max(mxsize, size[0] - size[u]);
  if (mxsize <= n / 2)
    return u;
  else
    return -1;
}
int best_path(int N, int K, int H[][2], int L[])
{
  for (int i = 0; i < N - 1; i++)
  {
    edge[H[i][0]].push_back(make_pair(H[i][1], L[i]));
    edge[H[i][1]].push_back(make_pair(H[i][0], L[i]));
  }
  k = K;
  n = N;

  cnt = 0;
  calc_size(0, -1);

  int rt = find_rt(0, -1);
  // cerr << rt << endl;
  depth[rt] = 1;
  dis[rt] = 0;
  init(rt, -1);

  // for (int i = 0; i < N; i++)
  // cout << dfn[i] << " ";
  // cout << endl;
  ans = N + 1;

  dfs1(rt, -1);

  if (ans == N + 1)
    return -1;
  return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs1(int, int)':
race.cpp:25:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edge[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~~
race.cpp:53:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edge[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void init(int, int)':
race.cpp:67:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edge[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'void calc_size(int, int)':
race.cpp:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edge[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~~
race.cpp: In function 'int find_rt(int, int)':
race.cpp:96:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edge[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~~

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