Submission #1116960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116960		repmann	Race (IOI11_race)	C++14	0 / 100	4 ms	14672 KiB

race

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
int N, K, sol = INF;
int SIZE[200006], DP[200006], W[200006], D[1000006];
bool V[200006];
vector <pair <int, int>> VG[200006];
inline void SDFS(int node, int parent = -1)
{
  SIZE[node] = 1;
  for(pair <int, int> p : VG[node])
  {
    if((p.second == parent) || V[p.second]) continue;
    SDFS(p.second, node);
    SIZE[node] += SIZE[p.second];
  }
  return;
}
inline int CDFS(int node, int n, int parent = -1)
{
  for(pair <int, int> p : VG[node])
  {
    if((p.second == parent) || V[p.second]) continue;
    if(SIZE[p.second] > n) return CDFS(p.second, n, node);
  }
  return node;
}
inline void DFS1(int node, int parent = -1)
{
  if(W[node] > K) return;
  sol = min(DP[node] + D[K - W[node]], sol);
  for(pair <int, int> p : VG[node])
  {
    if((p.second == parent) || V[p.second]) continue;
    DP[p.second] = DP[node] + 1;
    W[p.second] = W[node] + p.first;
    DFS1(p.second, node);
  }
  return;
}
inline void DFS2(int node, int parent = -1)
{
  if(W[node] > K) return;
  D[W[node]] = min(DP[node], D[W[node]]);
  for(pair <int, int> p : VG[node])
  {
    if((p.second == parent) || V[p.second]) continue;
    DFS2(p.second, node);
  }
  return;
}
inline void CLEARDFS(int node, int parent = -1)
{
  if(W[node] > K) return;
  D[W[node]] = INF;
  for(pair <int, int> p : VG[node])
  {
    if((p.second == parent) || V[p.second]) continue;
    CLEARDFS(p.second, node);
  }
  return;
}
inline void CD(int root)
{
  SDFS(root);
  int centroid = CDFS(root, SIZE[root] >> 1);
  V[centroid] = true;
  for(pair <int, int> p : VG[centroid])
  {
    if(V[p.second]) continue;
    DP[p.second] = 1;
    W[p.second] = p.first;
    DFS1(p.second, centroid);
    DFS2(p.second, centroid);
  }
  CLEARDFS(centroid);
  for(pair <int, int> p : VG[centroid]) if(!V[p.second]) CD(p.second);
}
int best_path(int n, int k, int (*H)[2], int* L)
{
  N = n;
  K = k;
  for(int i = 0; i < N - 1; i++)
  {
    VG[H[i][0] + 1].push_back({L[i], H[i][1] + 1});
    VG[H[i][1] + 1].push_back({L[i], H[i][0] + 1});
  }
  for(int i = 1; i <= 1000000; i++) D[i] = INF;
  CD(1);
  if(sol == INF) return -1;
  return sol;
}

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