oj.uz

Submission #1043984

# Submission time Handle Problem Language Result Execution time Memory
1043984 2024-08-05T05:43:47 Z dwuy Race (IOI11_race) C++14
100 / 100
 216 ms 43840 KB 
#include "race.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
 
struct Map{
    int sz, id;
    vector<int> vis;
    vector<int> val;

    Map(int n){
        this->sz = n;
        this->id = 1;
        this->vis.assign(n + 5, 0);
        this->val.assign(n + 5, 0);
    }

    void clear(){
        id++;
    }

    void add(int key, int val){
        this->vis[key] = id;
        this->val[key] = val;
    }

    int get(int key){
        return this->vis[key] == id? this->val[key] : 1e9;
    }
};

const int MX = 200005;
int n, k, ans = MX;
int numC[MX];
bitset<MX> vist;
vector<pii> G[MX];
 
void calChild(int u, int p){
    numC[u] = 1;
    for(pii &tmp: G[u]){
        int v, c;
        tie(v, c) = tmp;
        if(v==p || vist[v]) continue;
        calChild(v, u);
        numC[u] += numC[v];
    }
}
 
int Centroid(int u, int p, const int &half){
    for(pii &tmp: G[u]){
        int v = tmp.fi;
        if(v == p || vist[v]) continue;
        if(numC[v] > half) return Centroid(v, u, half);
    }
    return u;
}
 
int dis[MX];
int node[MX];
Map mp(1000005);
 
int calValue(int u){
    mp.clear();
    int res = MX;
    mp.add(0, 1);
    for(pii &tmp: G[u]){
        int v, c;
        tie(v, c) = tmp;
        if (vist[v]) continue;
        vector<int> path;
        stack<pii> Q;
        Q.push({v, u});
        node[v] = 2;
        dis[v] = c;
        while(Q.size()){
            int u, p;
            tie(u, p) = Q.top();
            Q.pop();
            path.push_back(u);
            for(pii &tmp: G[u]){
                int v, c;
                tie(v, c) = tmp;
                if(vist[v] || v == p) continue;
                Q.push({v, u});
                dis[v] = dis[u] + c;
                node[v] = node[u] + 1;
            }
        }
        for(int vt: path) if(dis[vt]<=k){
            int gm = mp.get(k - dis[vt]);
            if(gm) res = min(res, gm + node[vt] - 1);
        }
        for(int vt: path) if(dis[vt]<=k){
            mp.add(dis[vt], min(mp.get(dis[vt]), node[vt]));
        }
    }
    return res;
}
 
void buon(int u){
    calChild(u, 0);
    u = Centroid(u, 0, numC[u]>>1);
    ans = min(ans, calValue(u));
    vist[u] = 1;
    for(pii &tmp: G[u]){
        int v = tmp.fi;
        if(!vist[v]) buon(v);
    }
}
 
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];
        int v = H[i][1];
        int c = L[i];
        u++, v++;
        G[u].push_back({v, c});
        G[v].push_back({u, c});
    }
    buon(1);
    return ans==MX? -1 : ans - 1;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 3 ms 18524 KB Output is correct
4 Correct 3 ms 18524 KB Output is correct
5 Correct 4 ms 18524 KB Output is correct
6 Correct 4 ms 18524 KB Output is correct
7 Correct 3 ms 18524 KB Output is correct
8 Correct 3 ms 18524 KB Output is correct
9 Correct 3 ms 18524 KB Output is correct
10 Correct 3 ms 18524 KB Output is correct
11 Correct 3 ms 18524 KB Output is correct
12 Correct 3 ms 18524 KB Output is correct
13 Correct 3 ms 18524 KB Output is correct
14 Correct 4 ms 18524 KB Output is correct
15 Correct 3 ms 18524 KB Output is correct
16 Correct 3 ms 18524 KB Output is correct
17 Correct 3 ms 18524 KB Output is correct
18 Correct 3 ms 18524 KB Output is correct
19 Correct 4 ms 18524 KB Output is correct
20 Correct 3 ms 18524 KB Output is correct
21 Correct 4 ms 18524 KB Output is correct
22 Correct 3 ms 18524 KB Output is correct
23 Correct 5 ms 18520 KB Output is correct
24 Correct 4 ms 18524 KB Output is correct
25 Correct 3 ms 18524 KB Output is correct
26 Correct 4 ms 18476 KB Output is correct
27 Correct 4 ms 18520 KB Output is correct
28 Correct 4 ms 18524 KB Output is correct
29 Correct 3 ms 18524 KB Output is correct
30 Correct 3 ms 18524 KB Output is correct
31 Correct 4 ms 18524 KB Output is correct
32 Correct 4 ms 18524 KB Output is correct
33 Correct 4 ms 18524 KB Output is correct
34 Correct 4 ms 18592 KB Output is correct
35 Correct 4 ms 18524 KB Output is correct
36 Correct 5 ms 18524 KB Output is correct
37 Correct 4 ms 18524 KB Output is correct
38 Correct 3 ms 18524 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 3 ms 18524 KB Output is correct
4 Correct 3 ms 18524 KB Output is correct
5 Correct 4 ms 18524 KB Output is correct
6 Correct 4 ms 18524 KB Output is correct
7 Correct 3 ms 18524 KB Output is correct
8 Correct 3 ms 18524 KB Output is correct
9 Correct 3 ms 18524 KB Output is correct
10 Correct 3 ms 18524 KB Output is correct
11 Correct 3 ms 18524 KB Output is correct
12 Correct 3 ms 18524 KB Output is correct
13 Correct 3 ms 18524 KB Output is correct
14 Correct 4 ms 18524 KB Output is correct
15 Correct 3 ms 18524 KB Output is correct
16 Correct 3 ms 18524 KB Output is correct
17 Correct 3 ms 18524 KB Output is correct
18 Correct 3 ms 18524 KB Output is correct
19 Correct 75 ms 24872 KB Output is correct
20 Correct 73 ms 24716 KB Output is correct
21 Correct 70 ms 24908 KB Output is correct
22 Correct 62 ms 24912 KB Output is correct
23 Correct 65 ms 24892 KB Output is correct
24 Correct 45 ms 24784 KB Output is correct
25 Correct 87 ms 28432 KB Output is correct
26 Correct 68 ms 32080 KB Output is correct
27 Correct 102 ms 28756 KB Output is correct
28 Correct 197 ms 43840 KB Output is correct
29 Correct 199 ms 42560 KB Output is correct
30 Correct 92 ms 28692 KB Output is correct
31 Correct 95 ms 28752 KB Output is correct
32 Correct 108 ms 28752 KB Output is correct
33 Correct 146 ms 28428 KB Output is correct
34 Correct 199 ms 28296 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 3 ms 18524 KB Output is correct
4 Correct 3 ms 18524 KB Output is correct
5 Correct 4 ms 18524 KB Output is correct
6 Correct 4 ms 18524 KB Output is correct
7 Correct 3 ms 18524 KB Output is correct
8 Correct 3 ms 18524 KB Output is correct
9 Correct 3 ms 18524 KB Output is correct
10 Correct 3 ms 18524 KB Output is correct
11 Correct 3 ms 18524 KB Output is correct
12 Correct 3 ms 18524 KB Output is correct
13 Correct 3 ms 18524 KB Output is correct
14 Correct 4 ms 18524 KB Output is correct
15 Correct 3 ms 18524 KB Output is correct
16 Correct 3 ms 18524 KB Output is correct
17 Correct 3 ms 18524 KB Output is correct
18 Correct 3 ms 18524 KB Output is correct
19 Correct 4 ms 18524 KB Output is correct
20 Correct 3 ms 18524 KB Output is correct
21 Correct 4 ms 18524 KB Output is correct
22 Correct 3 ms 18524 KB Output is correct
23 Correct 5 ms 18520 KB Output is correct
24 Correct 4 ms 18524 KB Output is correct
25 Correct 3 ms 18524 KB Output is correct
26 Correct 4 ms 18476 KB Output is correct
27 Correct 4 ms 18520 KB Output is correct
28 Correct 4 ms 18524 KB Output is correct
29 Correct 3 ms 18524 KB Output is correct
30 Correct 3 ms 18524 KB Output is correct
31 Correct 4 ms 18524 KB Output is correct
32 Correct 4 ms 18524 KB Output is correct
33 Correct 4 ms 18524 KB Output is correct
34 Correct 4 ms 18592 KB Output is correct
35 Correct 4 ms 18524 KB Output is correct
36 Correct 5 ms 18524 KB Output is correct
37 Correct 4 ms 18524 KB Output is correct
38 Correct 3 ms 18524 KB Output is correct
39 Correct 75 ms 24872 KB Output is correct
40 Correct 73 ms 24716 KB Output is correct
41 Correct 70 ms 24908 KB Output is correct
42 Correct 62 ms 24912 KB Output is correct
43 Correct 65 ms 24892 KB Output is correct
44 Correct 45 ms 24784 KB Output is correct
45 Correct 87 ms 28432 KB Output is correct
46 Correct 68 ms 32080 KB Output is correct
47 Correct 102 ms 28756 KB Output is correct
48 Correct 197 ms 43840 KB Output is correct
49 Correct 199 ms 42560 KB Output is correct
50 Correct 92 ms 28692 KB Output is correct
51 Correct 95 ms 28752 KB Output is correct
52 Correct 108 ms 28752 KB Output is correct
53 Correct 146 ms 28428 KB Output is correct
54 Correct 199 ms 28296 KB Output is correct
55 Correct 8 ms 18776 KB Output is correct
56 Correct 9 ms 18780 KB Output is correct
57 Correct 52 ms 25120 KB Output is correct
58 Correct 29 ms 24524 KB Output is correct
59 Correct 67 ms 32088 KB Output is correct
60 Correct 216 ms 43220 KB Output is correct
61 Correct 98 ms 28756 KB Output is correct
62 Correct 94 ms 28752 KB Output is correct
63 Correct 109 ms 28752 KB Output is correct
64 Correct 191 ms 29136 KB Output is correct
65 Correct 142 ms 29140 KB Output is correct
66 Correct 211 ms 40000 KB Output is correct
67 Correct 56 ms 28864 KB Output is correct
68 Correct 115 ms 29392 KB Output is correct
69 Correct 119 ms 29472 KB Output is correct
70 Correct 108 ms 29312 KB Output is correct