oj.uz

Submission #130708

# Submission time Handle Problem Language Result Execution time Memory
130708 2019-07-16T00:02:41 Z jovan_b Race (IOI11_race) C++17
100 / 100
 1188 ms 173668 KB 
#include "race.h"
#include <bits/stdc++.h>

using namespace std;

int k;

typedef long long ll;

vector <int> ctree[1000005];
vector <pair <int, int>> graf[1000005];
bool visited[1000005];
bool bio[1000005];
int sz[1000005];
int dist[1000005];
int grane[1000005];
stack <int> qq;

int prvi;

void dfs1(int v){
    sz[v] = 1;
    visited[v] = 1;
    for(auto par : graf[v]){
        int c = par.first;
        if(!bio[c] && !visited[c]){
            dfs1(c);
            sz[v] += sz[c];
        }
    }
    visited[v] = 0;
}

int nadji(int v, int n, int par){
    for(auto pr : graf[v]){
        int c = pr.first;
        if(bio[c]) continue;
        if(c == par) continue;
        if(sz[c] > n/2) return nadji(c, n, v);
    }
    return v;
}

int mnn1[1000005];
int mnn2[1000005];

struct strukt{
    int first;
    int second;
    int third;
};

const int INF = 1000001;
int res = INF;

vector <strukt> sons[1000005];

void dfs2(int v, int dis, int brg, int root){
    visited[v] = 1;
    if(v != root) sons[root].push_back({dis, brg, v});
    for(auto pr : graf[v]){
        int c = pr.first;
        int x = pr.second;
        if(!visited[c] && !bio[c]){
            dfs2(c, min(INF, dis+x), brg+1, root);
        }
    }
    visited[v] = 0;
}

void decompose(){
    queue <pair <int, int>> q;
    q.push({1, 0});
    while(!q.empty()){
        int v = q.front().first;
        int parent = q.front().second;
        q.pop();
        dfs1(v);
        v = nadji(v, sz[v], 0);
        bio[v] = 1;
        dfs2(v, 0, 0, v);
        if(!parent) prvi = v;
        else{
            ctree[parent].push_back(v);
        }
        qq.push(v);
        for(auto pr : graf[v]){
            int c = pr.first;
            if(!bio[c]){
                q.push({c, v});
            }
        }
    }
}

void dfs3(){
    vector <int> vec[1000005];
    while(!qq.empty()){
        int cnt = 0;
        int v = qq.top();
        qq.pop();
        for(auto c : ctree[v]){
            sons[c].push_back({0, 0, c});
            cnt++;
            for(auto pr : sons[c]) vec[cnt].push_back(pr.third);
            sons[c].clear();
        }
        for(auto pr : sons[v]){
            int a = pr.first;
            int b = pr.second;
            int c = pr.third;
            dist[c] = a;
            grane[c] = b;
        }
        for(int i=1; i<=cnt; i++){
            for(auto gg : vec[i]){
                int a = dist[gg];
                int b = grane[gg];
                if(a == k) res = min(res, b);
                else if(a < k){
                    res = min(res, b + mnn1[k-a]);
                }
            }
            for(auto gg : vec[i]){
                int a = dist[gg];
                int b = grane[gg];
                if(a > k) continue;
                if(mnn1[a] >= b){
                    mnn2[a] = mnn1[a];
                    mnn1[a] = b;
                }
                else if(mnn2[a] > b){
                    mnn2[a] = b;
                }
            }
            vec[i].clear();
        }
        for(auto pr : sons[v]){
            if(pr.first > k) continue;
            mnn1[pr.first] = mnn2[pr.first] = INF;
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    int n = N;
    k = K;
    for(int i=0; i<n-1; i++){
        int a = H[i][0] + 1;
        int b = H[i][1] + 1;
        graf[a].push_back({b, L[i]});
        graf[b].push_back({a, L[i]});
    }
    decompose();
    for(int i=1; i<=n; i++) graf[i].clear();
    for(int i=1; i<=1000000; i++){
        mnn1[i] = mnn2[i] = INF;
    }
    dfs3();
    if(res == INF) return -1;
    return res;
}

/*int main(){
    int N, K, H[1000005][2], L[1000005];
    cin >> N >> K;
    for(int i=0; i<N; i++){
        cin >> H[i][0] >> H[i][1] >> L[i];
    }
    cout << best_path(N, K, H, L);
}*/
/*
10 6
0 1 3
1 2 2
2 3 2
3 4 3
4 5 2
5 6 2
6 7 1
7 8 2
8 9 2
*/
/*
3 2
0 1 1
1 2 1
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 102136 KB Output is correct
2 Correct 95 ms 102136 KB Output is correct
3 Correct 95 ms 102136 KB Output is correct
4 Correct 95 ms 102140 KB Output is correct
5 Correct 95 ms 102136 KB Output is correct
6 Correct 94 ms 102212 KB Output is correct
7 Correct 95 ms 102092 KB Output is correct
8 Correct 95 ms 102136 KB Output is correct
9 Correct 94 ms 102056 KB Output is correct
10 Correct 98 ms 102140 KB Output is correct
11 Correct 95 ms 102136 KB Output is correct
12 Correct 95 ms 102172 KB Output is correct
13 Correct 96 ms 102136 KB Output is correct
14 Correct 96 ms 102196 KB Output is correct
15 Correct 95 ms 102136 KB Output is correct
16 Correct 95 ms 102136 KB Output is correct
17 Correct 99 ms 102152 KB Output is correct
18 Correct 105 ms 102136 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 102136 KB Output is correct
2 Correct 95 ms 102136 KB Output is correct
3 Correct 95 ms 102136 KB Output is correct
4 Correct 95 ms 102140 KB Output is correct
5 Correct 95 ms 102136 KB Output is correct
6 Correct 94 ms 102212 KB Output is correct
7 Correct 95 ms 102092 KB Output is correct
8 Correct 95 ms 102136 KB Output is correct
9 Correct 94 ms 102056 KB Output is correct
10 Correct 98 ms 102140 KB Output is correct
11 Correct 95 ms 102136 KB Output is correct
12 Correct 95 ms 102172 KB Output is correct
13 Correct 96 ms 102136 KB Output is correct
14 Correct 96 ms 102196 KB Output is correct
15 Correct 95 ms 102136 KB Output is correct
16 Correct 95 ms 102136 KB Output is correct
17 Correct 99 ms 102152 KB Output is correct
18 Correct 105 ms 102136 KB Output is correct
19 Correct 94 ms 102136 KB Output is correct
20 Correct 95 ms 102108 KB Output is correct
21 Correct 97 ms 102264 KB Output is correct
22 Correct 99 ms 102264 KB Output is correct
23 Correct 97 ms 102436 KB Output is correct
24 Correct 96 ms 102264 KB Output is correct
25 Correct 113 ms 102392 KB Output is correct
26 Correct 120 ms 102364 KB Output is correct
27 Correct 116 ms 102392 KB Output is correct
28 Correct 99 ms 102332 KB Output is correct
29 Correct 97 ms 102392 KB Output is correct
30 Correct 99 ms 102392 KB Output is correct
31 Correct 98 ms 102392 KB Output is correct
32 Correct 97 ms 102392 KB Output is correct
33 Correct 97 ms 102380 KB Output is correct
34 Correct 97 ms 102520 KB Output is correct
35 Correct 96 ms 102264 KB Output is correct
36 Correct 97 ms 102484 KB Output is correct
37 Correct 96 ms 102392 KB Output is correct
38 Correct 96 ms 102264 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 102136 KB Output is correct
2 Correct 95 ms 102136 KB Output is correct
3 Correct 95 ms 102136 KB Output is correct
4 Correct 95 ms 102140 KB Output is correct
5 Correct 95 ms 102136 KB Output is correct
6 Correct 94 ms 102212 KB Output is correct
7 Correct 95 ms 102092 KB Output is correct
8 Correct 95 ms 102136 KB Output is correct
9 Correct 94 ms 102056 KB Output is correct
10 Correct 98 ms 102140 KB Output is correct
11 Correct 95 ms 102136 KB Output is correct
12 Correct 95 ms 102172 KB Output is correct
13 Correct 96 ms 102136 KB Output is correct
14 Correct 96 ms 102196 KB Output is correct
15 Correct 95 ms 102136 KB Output is correct
16 Correct 95 ms 102136 KB Output is correct
17 Correct 99 ms 102152 KB Output is correct
18 Correct 105 ms 102136 KB Output is correct
19 Correct 436 ms 129520 KB Output is correct
20 Correct 395 ms 129200 KB Output is correct
21 Correct 409 ms 128924 KB Output is correct
22 Correct 365 ms 126600 KB Output is correct
23 Correct 390 ms 132000 KB Output is correct
24 Correct 250 ms 121960 KB Output is correct
25 Correct 477 ms 136552 KB Output is correct
26 Correct 283 ms 136500 KB Output is correct
27 Correct 500 ms 143512 KB Output is correct
28 Correct 1058 ms 173468 KB Output is correct
29 Correct 1114 ms 173536 KB Output is correct
30 Correct 501 ms 143504 KB Output is correct
31 Correct 485 ms 143584 KB Output is correct
32 Correct 747 ms 143512 KB Output is correct
33 Correct 879 ms 165604 KB Output is correct
34 Correct 1000 ms 164308 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 102136 KB Output is correct
2 Correct 95 ms 102136 KB Output is correct
3 Correct 95 ms 102136 KB Output is correct
4 Correct 95 ms 102140 KB Output is correct
5 Correct 95 ms 102136 KB Output is correct
6 Correct 94 ms 102212 KB Output is correct
7 Correct 95 ms 102092 KB Output is correct
8 Correct 95 ms 102136 KB Output is correct
9 Correct 94 ms 102056 KB Output is correct
10 Correct 98 ms 102140 KB Output is correct
11 Correct 95 ms 102136 KB Output is correct
12 Correct 95 ms 102172 KB Output is correct
13 Correct 96 ms 102136 KB Output is correct
14 Correct 96 ms 102196 KB Output is correct
15 Correct 95 ms 102136 KB Output is correct
16 Correct 95 ms 102136 KB Output is correct
17 Correct 99 ms 102152 KB Output is correct
18 Correct 105 ms 102136 KB Output is correct
19 Correct 94 ms 102136 KB Output is correct
20 Correct 95 ms 102108 KB Output is correct
21 Correct 97 ms 102264 KB Output is correct
22 Correct 99 ms 102264 KB Output is correct
23 Correct 97 ms 102436 KB Output is correct
24 Correct 96 ms 102264 KB Output is correct
25 Correct 113 ms 102392 KB Output is correct
26 Correct 120 ms 102364 KB Output is correct
27 Correct 116 ms 102392 KB Output is correct
28 Correct 99 ms 102332 KB Output is correct
29 Correct 97 ms 102392 KB Output is correct
30 Correct 99 ms 102392 KB Output is correct
31 Correct 98 ms 102392 KB Output is correct
32 Correct 97 ms 102392 KB Output is correct
33 Correct 97 ms 102380 KB Output is correct
34 Correct 97 ms 102520 KB Output is correct
35 Correct 96 ms 102264 KB Output is correct
36 Correct 97 ms 102484 KB Output is correct
37 Correct 96 ms 102392 KB Output is correct
38 Correct 96 ms 102264 KB Output is correct
39 Correct 436 ms 129520 KB Output is correct
40 Correct 395 ms 129200 KB Output is correct
41 Correct 409 ms 128924 KB Output is correct
42 Correct 365 ms 126600 KB Output is correct
43 Correct 390 ms 132000 KB Output is correct
44 Correct 250 ms 121960 KB Output is correct
45 Correct 477 ms 136552 KB Output is correct
46 Correct 283 ms 136500 KB Output is correct
47 Correct 500 ms 143512 KB Output is correct
48 Correct 1058 ms 173468 KB Output is correct
49 Correct 1114 ms 173536 KB Output is correct
50 Correct 501 ms 143504 KB Output is correct
51 Correct 485 ms 143584 KB Output is correct
52 Correct 747 ms 143512 KB Output is correct
53 Correct 879 ms 165604 KB Output is correct
54 Correct 1000 ms 164308 KB Output is correct
55 Correct 115 ms 104412 KB Output is correct
56 Correct 125 ms 104444 KB Output is correct
57 Correct 282 ms 131980 KB Output is correct
58 Correct 161 ms 117472 KB Output is correct
59 Correct 288 ms 136564 KB Output is correct
60 Correct 1188 ms 173416 KB Output is correct
61 Correct 509 ms 143716 KB Output is correct
62 Correct 533 ms 143616 KB Output is correct
63 Correct 683 ms 143612 KB Output is correct
64 Correct 997 ms 157884 KB Output is correct
65 Correct 795 ms 153316 KB Output is correct
66 Correct 1173 ms 173668 KB Output is correct
67 Correct 357 ms 134108 KB Output is correct
68 Correct 626 ms 142264 KB Output is correct
69 Correct 631 ms 142332 KB Output is correct
70 Correct 588 ms 140404 KB Output is correct