Submission #253972

#	Time	Username	Problem	Language	Result	Execution time	Memory
253972		StevenH	Race (IOI11_race)	C++14	0 / 100	6 ms	9728 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int maxk = 1e6 + 5;
const int maxn = 2e5 + 5;
int dis[maxn], depth[maxn];
int n, k, cur;
int ans;
vector<vector<int> > pt(maxn);
vector<pair<int, int> > s;
vector<pair<int, int> > ss;
vector<vector<pair<int, int> > > edge(maxn);
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 < ss.size(); j++)
      {
        // s.push_back(ss[j]);
        pt[ss[j].first].push_back(ss[j].second);
      }
      ss.clear();
    }
  }
  if (flag == 0)
  {
    int dist = dis[u] - dis[rt];
    int dep = depth[u] - depth[rt];
    // cout << u << " " << depth[u] << " " << rt << " " << depth[rt] << endl;
    // cout << dist << " " << dep << endl;
    ss.push_back(make_pair(dis[u] - dis[rt], depth[u] - depth[rt]));
    if (k < dist)
      return;
    for (int i = 0; i < pt[k - dist].size(); i++)
      // cout << k - dist << " " << i << endl,
      ans = min(ans, dep + pt[k - dist][i]);
    // cout << ans << endl;
  }
  return;
}
void dfs1(int u, int f)
{
  cur++;
  // s.clear();
  pt.clear();
  // s.push_back(make_pair(0, 0));
  pt[0].push_back(0);
  dfs2(u, f, u);
  // for (int i = 0; i < s.size(); i++)
  //   cout << s[i].first << " " << s[i].second;
  // cout << endl;
  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)
{
  if (f != -1)
    depth[u] = depth[f] + 1;
  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;
    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 = 0;
  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:16:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edge[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~~
race.cpp:25:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0; j < ss.size(); j++)
                       ~~^~~~~~~~~~~
race.cpp:42:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < pt[k - dist].size(); i++)
                     ~~^~~~~~~~~~~~~~~~~~~~~
race.cpp: In function 'void dfs1(int, int)':
race.cpp:60:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < edge[u].size(); i++)
                   ~~^~~~~~~~~~~~~~~~
race.cpp:63: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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57