Submission #254454

#	Time	Username	Problem	Language	Result	Execution time	Memory
254454		StevenH	Race (IOI11_race)	C++14	100 / 100	679 ms	45560 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];
int n, k;
int vis[maxn];
int ans;
vector<vector<pair<int, int> > > edge(maxn);
int cur, tag[maxk], pt[maxk];
inline void reset(int dist)
{
  if (tag[dist] != cur)
  {
    tag[dist] = cur;
    pt[dist] = dist ? inf : 0;
  }
  return;
}
int dfn[maxn], last[maxn], rnk[maxn], cnt;
void init(int u, int f)
{
  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 || vis[v])
      continue;
    dis[v] = dis[u] + dist;
    depth[v] = depth[u] + 1;
    init(v, u);
  }
  last[u] = cnt;
  return;
}
int size[maxn], son[maxn], total;
void find_rt(int u, int f, int &root)
{
  size[u] = 1, son[u] = 0;
  for (int i = 0; i < edge[u].size(); i++)
  {
    int v = edge[u][i].first;
    if (f == v || vis[v])
      continue;
    find_rt(v, u, root);
    son[u] = max(son[u], size[v]);
    size[u] += size[v];
  }
  son[u] = max(son[u], total - size[u]);
  // cout << u << " " << son[u] << endl;
  if (root == -1 || son[u] < son[root])
    root = u;
  return;
}
void dfs1(int u)
{
  vis[u] = 1;
  cur++;
  // memset(pt, 0x3f, sizeof(pt));
  pt[0] = 0;
  for (int i = 0; i < edge[u].size(); i++)
  {
    int v = edge[u][i].first;
    if (vis[v])
      continue;
    for (int j = dfn[v]; j <= last[v]; j++)
    {
      int dist = dis[rnk[j]];
      int dep = depth[rnk[j]];
      if (dist > k)
        continue;
      reset(k - dist);
      ans = min(ans, dep + pt[k - dist]);
    }
    for (int j = dfn[v]; j <= last[v]; j++)
    {
      int dist = dis[rnk[j]];
      int dep = depth[rnk[j]];

      if (dist > k)
        continue;
      reset(dist);
      pt[dist] = min(pt[dist], dep);
    }
  }
  for (int i = 0; i < edge[u].size(); i++)
  {
    int v = edge[u][i].first;
    if (vis[v])
      continue;
    int rt = -1;
    total = size[v];
    find_rt(v, -1, rt);
    // cerr << rt << endl;
    depth[rt] = 0;
    dis[rt] = 0;
    cnt = 0;
    init(rt, -1);
    dfs1(rt);
  }
  return;
}
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;

  ans = N + 1;

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

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

Compilation message (stderr)

race.cpp: In function 'void init(int, int)':
race.cpp:27: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 find_rt(int, int, int&)':
race.cpp:44: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 dfs1(int)':
race.cpp:65:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edge[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~~
race.cpp:90: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: 22 / 22
• Subtask 4: 57 / 57