oj.uz

Submission #1038067

# Submission time Handle Problem Language Result Execution time Memory
1038067 2024-07-29T12:39:16 Z karok Race (IOI11_race) C++17
9 / 100
 3000 ms 23936 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 = min(dfs(centroid, 0, 0, lengths), 0ll + INT_MAX);
        // 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 2 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 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 3 ms 9048 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 2 ms 9048 KB Output is correct
14 Correct 2 ms 9052 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9072 KB Output is correct
17 Correct 4 ms 9052 KB Output is correct
18 Correct 2 ms 9052 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 2 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 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 3 ms 9048 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 2 ms 9048 KB Output is correct
14 Correct 2 ms 9052 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9072 KB Output is correct
17 Correct 4 ms 9052 KB Output is correct
18 Correct 2 ms 9052 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 9308 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 2 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 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 3 ms 9048 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 2 ms 9048 KB Output is correct
14 Correct 2 ms 9052 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9072 KB Output is correct
17 Correct 4 ms 9052 KB Output is correct
18 Correct 2 ms 9052 KB Output is correct
19 Correct 328 ms 16984 KB Output is correct
20 Correct 360 ms 16976 KB Output is correct
21 Correct 264 ms 16980 KB Output is correct
22 Correct 209 ms 17108 KB Output is correct
23 Correct 406 ms 17572 KB Output is correct
24 Correct 146 ms 16636 KB Output is correct
25 Execution timed out 3079 ms 23936 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 2 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 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 3 ms 9048 KB Output is correct
12 Correct 2 ms 9052 KB Output is correct
13 Correct 2 ms 9048 KB Output is correct
14 Correct 2 ms 9052 KB Output is correct
15 Correct 2 ms 9052 KB Output is correct
16 Correct 2 ms 9072 KB Output is correct
17 Correct 4 ms 9052 KB Output is correct
18 Correct 2 ms 9052 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 9308 KB Output isn't correct
22 Halted 0 ms 0 KB -