oj.uz

Submission #1038053

# Submission time Handle Problem Language Result Execution time Memory
1038053 2024-07-29T12:31:53 Z karok Race (IOI11_race) C++17
9 / 100
 3000 ms 25220 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

struct Edges {
    int target, weight;
};
struct Node {
    int value = INT_MAX;
};

const int MAXN = 200000 + 200;
const int MAXK = 1000000 + 200;

int n, k;
vector<vector<Edges>> adj(MAXN);
int tree_size[MAXN] = {};
bool is_removed[MAXN] = {};

int get_tree_size(int cur_vertex, int parent = -1) {
    int &res = tree_size[cur_vertex];
    res = 1;
    for (auto [v, w] : adj[cur_vertex]) {
        if (v == parent || is_removed[v])continue;
            continue;
        res += get_tree_size(v, cur_vertex);
    }
    return res;
}

int get_centroid(int cur_vertex, int n, int parent = -1) {
    for (auto [v, w] : adj[cur_vertex]) {
        if (parent == v || is_removed[v])
            continue;
        if (tree_size[v] * 2 > n)
            return get_centroid(v, n, cur_vertex);
    }
    return cur_vertex;
}

int dfs(int cur_v,int cur_length, int total_ans, map<int,Node> &past_lengths, int parent = -1){
    int res = past_lengths[k - cur_length].value + total_ans;
    for(auto [v, w]: adj[cur_v]){
        if(v == parent || is_removed[v]) continue;
        res = min(dfs(v, w + cur_length, total_ans + 1, past_lengths, cur_v), res);
    }
    past_lengths[cur_length].value = min(past_lengths[cur_length].value, total_ans);
    return res;
}

int centroid_dfs(int cur_v) {
    int centroid = get_centroid(cur_v, get_tree_size(cur_v));
    int res;
    {
        map<int,Node> lengths;
        lengths[0].value = 0;
        res = dfs(centroid, 0, 0, lengths);
    }
    is_removed[centroid] = true;
    for(auto [u, w]: adj[centroid]) {
        if(is_removed[u])continue;
        res = min(centroid_dfs(u), res);
    }
    return res;
}

#undef int
int best_path(int a, int b, int h[][2] ,int l[] ) {
    n = a; k= b;
    for(int i =0;i < n - 1;i++) {
        adj[h[i][0]].push_back( Edges{h[i][1], l[i]} );
        adj[h[i][1]].push_back( Edges{h[i][0], l[i]} );
    }
    int ans = centroid_dfs(0);
    if(ans == INT_MAX) return -1;
    else return ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9048 KB Output is correct
2 Correct 4 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 3 ms 9244 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 3 ms 9052 KB Output is correct
12 Correct 3 ms 9052 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 3 ms 9052 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9040 KB Output is correct
18 Correct 2 ms 9048 KB Output is correct
19 Correct 2 ms 9052 KB Output is correct
20 Correct 2 ms 9052 KB Output is correct
21 Incorrect 4 ms 9304 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9048 KB Output is correct
2 Correct 4 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 3 ms 9244 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 3 ms 9052 KB Output is correct
12 Correct 3 ms 9052 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 3 ms 9052 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9040 KB Output is correct
18 Correct 2 ms 9048 KB Output is correct
19 Correct 339 ms 16860 KB Output is correct
20 Correct 404 ms 18256 KB Output is correct
21 Correct 262 ms 18420 KB Output is correct
22 Correct 200 ms 18520 KB Output is correct
23 Correct 431 ms 19284 KB Output is correct
24 Correct 159 ms 17988 KB Output is correct
25 Execution timed out 3044 ms 25220 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9048 KB Output is correct
2 Correct 4 ms 9052 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9052 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9052 KB Output is correct
9 Correct 3 ms 9244 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 3 ms 9052 KB Output is correct
12 Correct 3 ms 9052 KB Output is correct
13 Correct 3 ms 9052 KB Output is correct
14 Correct 3 ms 9052 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9052 KB Output is correct
17 Correct 2 ms 9040 KB Output is correct
18 Correct 2 ms 9048 KB Output is correct
19 Correct 2 ms 9052 KB Output is correct
20 Correct 2 ms 9052 KB Output is correct
21 Incorrect 4 ms 9304 KB Output isn't correct
22 Halted 0 ms 0 KB -