oj.uz

Submission #1116960

# Submission time Handle Problem Language Result Execution time Memory
1116960 2024-11-22T16:26:17 Z repmann Race (IOI11_race) C++14
0 / 100
 4 ms 14672 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14672 KB Output is correct
2 Correct 3 ms 14672 KB Output is correct
3 Correct 4 ms 14672 KB Output is correct
4 Correct 3 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Incorrect 4 ms 14672 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14672 KB Output is correct
2 Correct 3 ms 14672 KB Output is correct
3 Correct 4 ms 14672 KB Output is correct
4 Correct 3 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Incorrect 4 ms 14672 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14672 KB Output is correct
2 Correct 3 ms 14672 KB Output is correct
3 Correct 4 ms 14672 KB Output is correct
4 Correct 3 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Incorrect 4 ms 14672 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14672 KB Output is correct
2 Correct 3 ms 14672 KB Output is correct
3 Correct 4 ms 14672 KB Output is correct
4 Correct 3 ms 14672 KB Output is correct
5 Correct 3 ms 14672 KB Output is correct
6 Correct 3 ms 14672 KB Output is correct
7 Incorrect 4 ms 14672 KB Output isn't correct
8 Halted 0 ms 0 KB -