oj.uz

Submission #1115369

# Submission time Handle Problem Language Result Execution time Memory
1115369 2024-11-20T11:49:34 Z gustavo_d Race (IOI11_race) C++17
9 / 100
 3000 ms 24884 KB 
// #include "race.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
 
const int MAXN = 2e5;
const int MAXV = 1e2+1;
vector<pair<int, int>> adj[MAXN];
bool vis[MAXN];
int sz[MAXN];
bool in[MAXN];
 
int n, k;
 
void dfs(int v, int pai) {
    sz[v] = 1;
    for (auto& [viz, w] : adj[v]) {
        if (viz == pai or in[viz]) continue;
        dfs(viz, v);
        sz[v] += sz[viz];
    }
}
 
int find_centroid(int v, int pai, int qty) {
    // cout << "buscando centroid " << v << endl;
    for (auto& [viz, w] : adj[v]) {
        if (viz == pai or in[viz]) continue;
        if (sz[viz] > qty / 2) find_centroid(viz, v, qty);
    }
    // cout << "é" << v <<endl;
    return v;
}
 
vector<int> sub_mn_depth(MAXV, 1e8);
vector<int> dists(MAXV, 1e8);
vector<int> sub_dists;
void get_dist(int v, int pai, int dist, int depth) {
    if (dist > k) return;
    sub_mn_depth[dist] = min(sub_mn_depth[dist], depth);
    sub_dists.push_back(dist);
    for (auto& [viz, w] : adj[v]) {
        if (viz == pai or in[viz]) continue;
        get_dist(viz, v, dist + w, depth+1);
    }
}
 
int ans = 1e8;
void decomp(int v) {
    dfs(v, -1);
    int centroid = find_centroid(v, -1, sz[v]);
    in[centroid] = true;
    vector<int> all_dists;
    // if (centroid == 8) cout << centroid << " é centroid decompondo" << v << endl;
    for (auto& [viz, w] : adj[centroid]) {
        if (in[viz]) continue;
        get_dist(viz, centroid, w, 1);
        for (int d : sub_dists) { // só considera prefixo de subárvores
            ans = min(ans, dists[k-d] + sub_mn_depth[d]);
        }
        for (int d : sub_dists) {
            dists[d] = min(dists[d], sub_mn_depth[d]);
            all_dists.push_back(d);
            sub_mn_depth[d] = 1e8;
        }
        sub_dists.clear();
    }
    ans = min(ans, dists[k]);
    for (int d : all_dists) dists[d] = 1e8;
    for (auto& [viz, w] : adj[centroid]) {
        if (in[viz]) continue;
        decomp(viz);
    }
}
 
int best_path(int N, int K, int H[][2], int L[]) {
    n = N; k = K;
    for (int i=0; i<N-1; i++) {
        int u = H[i][0], v = H[i][1];
        int w = L[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
 
    decomp(0);
 
    return (ans == (int)1e8 ? -1 : ans);
}

Subtask #1
9.0 / 9.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9808 KB Output is correct
2 Correct 3 ms 9808 KB Output is correct
3 Correct 3 ms 9808 KB Output is correct
4 Correct 3 ms 9808 KB Output is correct
5 Correct 3 ms 9808 KB Output is correct
6 Correct 2 ms 9808 KB Output is correct
7 Correct 4 ms 9948 KB Output is correct
8 Correct 3 ms 9808 KB Output is correct
9 Correct 3 ms 9808 KB Output is correct
10 Correct 3 ms 9808 KB Output is correct
11 Correct 3 ms 9808 KB Output is correct
12 Correct 2 ms 9808 KB Output is correct
13 Correct 3 ms 9976 KB Output is correct
14 Correct 3 ms 9808 KB Output is correct
15 Correct 3 ms 9808 KB Output is correct
16 Correct 3 ms 9808 KB Output is correct
17 Correct 3 ms 9820 KB Output is correct
18 Correct 3 ms 9808 KB Output is correct
19 Correct 2 ms 10064 KB Output is correct
20 Correct 3 ms 9808 KB Output is correct
21 Runtime error 17 ms 20048 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9808 KB Output is correct
2 Correct 3 ms 9808 KB Output is correct
3 Correct 3 ms 9808 KB Output is correct
4 Correct 3 ms 9808 KB Output is correct
5 Correct 3 ms 9808 KB Output is correct
6 Correct 2 ms 9808 KB Output is correct
7 Correct 4 ms 9948 KB Output is correct
8 Correct 3 ms 9808 KB Output is correct
9 Correct 3 ms 9808 KB Output is correct
10 Correct 3 ms 9808 KB Output is correct
11 Correct 3 ms 9808 KB Output is correct
12 Correct 2 ms 9808 KB Output is correct
13 Correct 3 ms 9976 KB Output is correct
14 Correct 3 ms 9808 KB Output is correct
15 Correct 3 ms 9808 KB Output is correct
16 Correct 3 ms 9808 KB Output is correct
17 Correct 3 ms 9820 KB Output is correct
18 Correct 3 ms 9808 KB Output is correct
19 Correct 161 ms 16272 KB Output is correct
20 Correct 155 ms 16356 KB Output is correct
21 Correct 129 ms 17004 KB Output is correct
22 Correct 102 ms 18056 KB Output is correct
23 Correct 59 ms 16076 KB Output is correct
24 Correct 43 ms 15952 KB Output is correct
25 Execution timed out 3061 ms 24884 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 9808 KB Output is correct
2 Correct 3 ms 9808 KB Output is correct
3 Correct 3 ms 9808 KB Output is correct
4 Correct 3 ms 9808 KB Output is correct
5 Correct 3 ms 9808 KB Output is correct
6 Correct 2 ms 9808 KB Output is correct
7 Correct 4 ms 9948 KB Output is correct
8 Correct 3 ms 9808 KB Output is correct
9 Correct 3 ms 9808 KB Output is correct
10 Correct 3 ms 9808 KB Output is correct
11 Correct 3 ms 9808 KB Output is correct
12 Correct 2 ms 9808 KB Output is correct
13 Correct 3 ms 9976 KB Output is correct
14 Correct 3 ms 9808 KB Output is correct
15 Correct 3 ms 9808 KB Output is correct
16 Correct 3 ms 9808 KB Output is correct
17 Correct 3 ms 9820 KB Output is correct
18 Correct 3 ms 9808 KB Output is correct
19 Correct 2 ms 10064 KB Output is correct
20 Correct 3 ms 9808 KB Output is correct
21 Runtime error 17 ms 20048 KB Execution killed with signal 6
22 Halted 0 ms 0 KB -