Submission #384441

#	Time	Username	Problem	Language	Result	Execution time	Memory
384441		apostoldaniel854	Race (IOI11_race)	C++14	0 / 100	4 ms	5100 KiB

race

#include <bits/stdc++.h>

using namespace std;

//#define HOME

#ifndef HOME
#include "race.h"
#endif // HOME

const int MAX_N = 2e5;
bool used[1 + MAX_N];
int sz[1 + MAX_N];
vector <pair <int, int>> gr[1 + MAX_N];
int k;
const int INF = 1e9;
void dfs_sz (int node, int par) {
    sz[node] = 1;
    for (auto it : gr[node]) {
        int son = it.first;
        if (not used[son] && son != par) {
            dfs_sz (son, node);
            sz[node] += sz[son];
        }
    }
}

int get_centroid (int node, int par, int target) {
    for (auto it : gr[node]) {
        int son = it.first;
        if (sz[son] > target && not used[son] && son != par)
            return get_centroid (son, node, target);
    }
    return node;
}
int best[1 + MAX_N];

void add_paths (int node, int par, int sum, int depth, int bound) {
    if (sum > bound)
        return;
    if (best[sum] > depth)
        best[sum] = depth;
    for (auto it : gr[node]) {
        int son = it.first;
        int cost = it.second;
        if (not used[son] && par != son)
            add_paths (son, node, sum + cost, depth + 1, bound);
    }
}
int ans;
void query_paths (int node, int par, int sum, int depth, int bound) {
    if (sum > bound)
        return;
    if (best[bound - sum] + depth < ans)
        ans = best[bound - sum] + depth;
    for (auto it : gr[node]) {
        int son = it.first;
        int cost = it.second;
        if (not used[son] && par != son)
            query_paths (son, node, sum + cost, depth + 1, bound);
    }
}
void delete_paths (int node, int par, int sum, int bound) {
    if (sum > bound)
        return;
    best[sum] = INF;
    for (auto it : gr[node]) {
        int son = it.first;
        int cost = it.second;
        if (not used[son] && par != son)
            delete_paths (son, node, sum + cost, bound);
    }
}
void solve (int node) {
    /// find centroid
    dfs_sz (node, -1);
    int centroid = get_centroid (node, -1, sz[node] / 2);

    /// add

    for (auto it : gr[centroid]) {
        int son = it.first;
        int cost = it.second;
        if (not used[son]) {
            query_paths (son, centroid, cost, 1, k);
            add_paths (son, centroid, cost, 1, k);
        }
    }

    /// delete
    delete_paths (node, -1, 0, k);
    /// go in subtrees
    used[centroid] = true;
    for (auto it : gr[centroid]) {
        int son = it.first;
        if (not used[son])
            solve (son);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    k = K;
    for (int i = 0; i <= K; i++)
        best[i] = INF;
    for (int i = 0; i < N - 1; i++) {
        int x = H[i][0], y = H[i][1], c = L[i];
        gr[x].push_back ({y, c});
        gr[y].push_back ({x, c});
    }
    ans = INF;
    solve (0);
    if (ans == INF)
        ans = -1;
    return ans;
}
/**
3 3
0 1 1
1 2 1
-1


**/



#ifdef HOME
#define MAX_N 500000


static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;

inline
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(2==scanf("%d %d",&N,&K));
  for(i=0; i<N-1; i++)
    my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = best_path(N,K,H,L);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}
#endif // HOME

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