oj.uz

Submission #384449

# Submission time Handle Problem Language Result Execution time Memory
384449 2021-04-01T17:05:50 Z apostoldaniel854 Race (IOI11_race) C++14
100 / 100
 690 ms 36332 KB 
#include <bits/stdc++.h>

using namespace std;

//#define HOME

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

const int MAX_N = 2e5, MAX_K = 1e6;
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_K];

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);
    best[0] = 0;
    /// 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 (centroid, -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 = 1; 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;
}
/**
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2




**/



#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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 4 ms 5248 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 4 ms 5100 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 4 ms 5100 KB Output is correct
16 Correct 4 ms 5100 KB Output is correct
17 Correct 4 ms 5248 KB Output is correct
18 Correct 4 ms 5100 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 4 ms 5248 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 4 ms 5100 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 4 ms 5100 KB Output is correct
16 Correct 4 ms 5100 KB Output is correct
17 Correct 4 ms 5248 KB Output is correct
18 Correct 4 ms 5100 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Correct 4 ms 5100 KB Output is correct
21 Correct 4 ms 5100 KB Output is correct
22 Correct 7 ms 8684 KB Output is correct
23 Correct 6 ms 8044 KB Output is correct
24 Correct 7 ms 8556 KB Output is correct
25 Correct 7 ms 8428 KB Output is correct
26 Correct 5 ms 6380 KB Output is correct
27 Correct 8 ms 8300 KB Output is correct
28 Correct 6 ms 5868 KB Output is correct
29 Correct 6 ms 6380 KB Output is correct
30 Correct 5 ms 6508 KB Output is correct
31 Correct 6 ms 7660 KB Output is correct
32 Correct 8 ms 7936 KB Output is correct
33 Correct 7 ms 8172 KB Output is correct
34 Correct 6 ms 7404 KB Output is correct
35 Correct 8 ms 8300 KB Output is correct
36 Correct 7 ms 8812 KB Output is correct
37 Correct 7 ms 8172 KB Output is correct
38 Correct 6 ms 7148 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 4 ms 5248 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 4 ms 5100 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 4 ms 5100 KB Output is correct
16 Correct 4 ms 5100 KB Output is correct
17 Correct 4 ms 5248 KB Output is correct
18 Correct 4 ms 5100 KB Output is correct
19 Correct 162 ms 11756 KB Output is correct
20 Correct 175 ms 11756 KB Output is correct
21 Correct 225 ms 11756 KB Output is correct
22 Correct 218 ms 11884 KB Output is correct
23 Correct 90 ms 12140 KB Output is correct
24 Correct 69 ms 12012 KB Output is correct
25 Correct 143 ms 15340 KB Output is correct
26 Correct 111 ms 19072 KB Output is correct
27 Correct 212 ms 18948 KB Output is correct
28 Correct 286 ms 33260 KB Output is correct
29 Correct 296 ms 32108 KB Output is correct
30 Correct 216 ms 18796 KB Output is correct
31 Correct 236 ms 18796 KB Output is correct
32 Correct 251 ms 18924 KB Output is correct
33 Correct 244 ms 17772 KB Output is correct
34 Correct 212 ms 18848 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 4 ms 5100 KB Output is correct
7 Correct 4 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 4 ms 5100 KB Output is correct
10 Correct 4 ms 5100 KB Output is correct
11 Correct 4 ms 5248 KB Output is correct
12 Correct 4 ms 5100 KB Output is correct
13 Correct 4 ms 5100 KB Output is correct
14 Correct 4 ms 5100 KB Output is correct
15 Correct 4 ms 5100 KB Output is correct
16 Correct 4 ms 5100 KB Output is correct
17 Correct 4 ms 5248 KB Output is correct
18 Correct 4 ms 5100 KB Output is correct
19 Correct 4 ms 5100 KB Output is correct
20 Correct 4 ms 5100 KB Output is correct
21 Correct 4 ms 5100 KB Output is correct
22 Correct 7 ms 8684 KB Output is correct
23 Correct 6 ms 8044 KB Output is correct
24 Correct 7 ms 8556 KB Output is correct
25 Correct 7 ms 8428 KB Output is correct
26 Correct 5 ms 6380 KB Output is correct
27 Correct 8 ms 8300 KB Output is correct
28 Correct 6 ms 5868 KB Output is correct
29 Correct 6 ms 6380 KB Output is correct
30 Correct 5 ms 6508 KB Output is correct
31 Correct 6 ms 7660 KB Output is correct
32 Correct 8 ms 7936 KB Output is correct
33 Correct 7 ms 8172 KB Output is correct
34 Correct 6 ms 7404 KB Output is correct
35 Correct 8 ms 8300 KB Output is correct
36 Correct 7 ms 8812 KB Output is correct
37 Correct 7 ms 8172 KB Output is correct
38 Correct 6 ms 7148 KB Output is correct
39 Correct 162 ms 11756 KB Output is correct
40 Correct 175 ms 11756 KB Output is correct
41 Correct 225 ms 11756 KB Output is correct
42 Correct 218 ms 11884 KB Output is correct
43 Correct 90 ms 12140 KB Output is correct
44 Correct 69 ms 12012 KB Output is correct
45 Correct 143 ms 15340 KB Output is correct
46 Correct 111 ms 19072 KB Output is correct
47 Correct 212 ms 18948 KB Output is correct
48 Correct 286 ms 33260 KB Output is correct
49 Correct 296 ms 32108 KB Output is correct
50 Correct 216 ms 18796 KB Output is correct
51 Correct 236 ms 18796 KB Output is correct
52 Correct 251 ms 18924 KB Output is correct
53 Correct 244 ms 17772 KB Output is correct
54 Correct 212 ms 18848 KB Output is correct
55 Correct 13 ms 5740 KB Output is correct
56 Correct 18 ms 5740 KB Output is correct
57 Correct 95 ms 12012 KB Output is correct
58 Correct 43 ms 11744 KB Output is correct
59 Correct 117 ms 19820 KB Output is correct
60 Correct 604 ms 36332 KB Output is correct
61 Correct 232 ms 19052 KB Output is correct
62 Correct 257 ms 22764 KB Output is correct
63 Correct 370 ms 22872 KB Output is correct
64 Correct 690 ms 21228 KB Output is correct
65 Correct 272 ms 19692 KB Output is correct
66 Correct 495 ms 33772 KB Output is correct
67 Correct 148 ms 23516 KB Output is correct
68 Correct 343 ms 23532 KB Output is correct
69 Correct 372 ms 23704 KB Output is correct
70 Correct 317 ms 23148 KB Output is correct