Submission #253988

#	Time	Username	Problem	Language	Result	Execution time	Memory
253988		StevenH	Race (IOI11_race)	C++14	21 / 100	3081 ms	20416 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];
int n, k, cur;
int ans;
vector<int> pt(maxk);
vector<pair<int, int> > s;
vector<vector<pair<int, int> > > edge(maxn);
inline void reset(int dist)
{
  if (tag[dist] != cur)
  {
    tag[dist] = cur;
    if (dist)
      pt[dist] = inf;
    else
      pt[dist] = 0;
  }
}
void dfs2(int u, int f, int rt)
{
  int flag = 0;
  for (int i = 0; i < edge[u].size(); i++)
  {
    int v = edge[u][i].first;
    if (v == f)
      continue;
    flag = 1;
    dfs2(v, u, rt);
    if (u == rt)
    {
      for (int j = 0; j < s.size(); j++)
      {
        int dist = s[j].first;
        int dep = s[j].second;
        reset(dist);
        pt[dist] = min(pt[dist], dep);
      }
      s.clear();
    }
  }

  int dist = dis[u] - dis[rt];
  int dep = depth[u] - depth[rt];
  if (k < dist)
    return;
  s.push_back(make_pair(dis[u] - dis[rt], depth[u] - depth[rt]));
  reset(k - dist);
  ans = min(ans, dep + pt[k - dist]);

  return;
}
void dfs1(int u, int f)
{
  s.clear();
  cur++;
  dfs2(u, f, u);
  for (int i = 0; i < edge[u].size(); i++)
  {
    int v = edge[u][i].first;
    int dist = edge[u][i].second;
    if (v == f)
      continue;
    dfs1(v, u);
  }
  return;
}
void init(int u, int f)
{
  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);
  }
  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;

  int rt = rand() % N;
  depth[rt] = 1;
  dis[rt] = 0;
  init(rt, -1);

  ans = N + 1;

  dfs1(rt, -1);

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

Compilation message (stderr)

race.cpp: In function 'void dfs2(int, 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:36:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < s.size(); j++)
                       ~~^~~~~~~~~~
race.cpp:26:7: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
   int flag = 0;
       ^~~~
race.cpp: In function 'void dfs1(int, int)':
race.cpp:62:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edge[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~~
race.cpp:65:9: warning: unused variable 'dist' [-Wunused-variable]
     int dist = edge[u][i].second;
         ^~~~
race.cpp: In function 'void init(int, int)':
race.cpp:74: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