oj.uz

Submission #1064665

# Submission time Handle Problem Language Result Execution time Memory
1064665 2024-08-18T16:35:54 Z Hugo1729 Race (IOI11_race) C++11
21 / 100
 1672 ms 262144 KB 
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;

vector<pair<ll,ll>> adj[1000001];
ll sz[1000001];
bool marked[1000001]={0};

ll k;

ll dfs_sizes(ll v, ll pV){
    sz[v]=0;
    for(auto [w,d] : adj[v]){
        if(w!=pV&&!marked[w]){
            sz[v]+=dfs_sizes(w,v);
        }
    }
    return sz[v];
}

ll dfs_centroid(ll v, ll pV, ll subtree_sz){
    for(auto [w,d] : adj[v]){
        if(pV!=w&&!marked[w]&&sz[w]>=(subtree_sz/2)){
            return dfs_centroid(w,v,subtree_sz);
        }
    }
    return v;
}

void dfs_paths(ll v, ll pV,ll dist,ll l, vector<pair<ll,ll>> &a){
    for(auto [w,d] : adj[v]){
        if(w!=pV&&!marked[w]){
            if(dist+d<=1000000){
                a.push_back({dist+d,l+1});
                dfs_paths(w,v,dist+d,l+1,a);
            }
        }
    }
}


ll centroid_decomposition(ll v){
    ll c = dfs_centroid(v,v,dfs_sizes(v,v));


    marked[c]=1;
    
    ll ans=1000001;
    map<ll,ll> m;
    m[0]=0;

    for(auto [w,d] : adj[c]){
        if(!marked[w]){
            vector<pair<ll,ll>> a;
            dfs_paths(w,c,d,1,a);

            for(auto [dist,l] : a){
                if(m.count(k-dist)){
                    ans=min(ans,l+m[k-dist]);
                }
            }
            for(auto [dist,l] : a){
                if(m.count(dist))m[dist]=min(m[dist],l);
                else m[dist]=l;
            }



            ans = min(ans,centroid_decomposition(w));
        }
    }

    return ans;
}




int best_path(int N, int K, int H[][2], int L[]){
    for(ll i=0;i<N-1;i++){
        adj[H[i][0]].push_back({H[i][1],L[i]});
        adj[H[i][1]].push_back({H[i][0],L[i]});
    }

    k=K;
    ll ans = centroid_decomposition(0);

    return (ans==1000001?-1:ans);
}

Compilation message

race.cpp: In function 'll dfs_sizes(ll, ll)':
race.cpp:14:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto [w,d] : adj[v]){
      |              ^
race.cpp: In function 'll dfs_centroid(ll, ll, ll)':
race.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |     for(auto [w,d] : adj[v]){
      |              ^
race.cpp: In function 'void dfs_paths(ll, ll, ll, ll, std::vector<std::pair<long long int, long long int> >&)':
race.cpp:32:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for(auto [w,d] : adj[v]){
      |              ^
race.cpp: In function 'll centroid_decomposition(ll)':
race.cpp:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |     for(auto [w,d] : adj[c]){
      |              ^
race.cpp:58:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |             for(auto [dist,l] : a){
      |                      ^
race.cpp:63:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |             for(auto [dist,l] : a){
      |                      ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 30556 KB Output is correct
2 Correct 6 ms 30652 KB Output is correct
3 Correct 5 ms 30552 KB Output is correct
4 Correct 5 ms 30296 KB Output is correct
5 Correct 5 ms 30040 KB Output is correct
6 Correct 5 ms 30416 KB Output is correct
7 Correct 5 ms 30556 KB Output is correct
8 Correct 5 ms 30552 KB Output is correct
9 Correct 5 ms 30556 KB Output is correct
10 Correct 5 ms 30660 KB Output is correct
11 Correct 5 ms 30556 KB Output is correct
12 Correct 5 ms 30556 KB Output is correct
13 Correct 5 ms 30612 KB Output is correct
14 Correct 5 ms 30556 KB Output is correct
15 Correct 5 ms 30296 KB Output is correct
16 Correct 5 ms 30556 KB Output is correct
17 Correct 5 ms 30556 KB Output is correct
18 Correct 5 ms 30556 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 30556 KB Output is correct
2 Correct 6 ms 30652 KB Output is correct
3 Correct 5 ms 30552 KB Output is correct
4 Correct 5 ms 30296 KB Output is correct
5 Correct 5 ms 30040 KB Output is correct
6 Correct 5 ms 30416 KB Output is correct
7 Correct 5 ms 30556 KB Output is correct
8 Correct 5 ms 30552 KB Output is correct
9 Correct 5 ms 30556 KB Output is correct
10 Correct 5 ms 30660 KB Output is correct
11 Correct 5 ms 30556 KB Output is correct
12 Correct 5 ms 30556 KB Output is correct
13 Correct 5 ms 30612 KB Output is correct
14 Correct 5 ms 30556 KB Output is correct
15 Correct 5 ms 30296 KB Output is correct
16 Correct 5 ms 30556 KB Output is correct
17 Correct 5 ms 30556 KB Output is correct
18 Correct 5 ms 30556 KB Output is correct
19 Correct 4 ms 29988 KB Output is correct
20 Correct 5 ms 30408 KB Output is correct
21 Correct 78 ms 55144 KB Output is correct
22 Correct 9 ms 30556 KB Output is correct
23 Correct 9 ms 30500 KB Output is correct
24 Correct 9 ms 30812 KB Output is correct
25 Correct 105 ms 71688 KB Output is correct
26 Correct 15 ms 33628 KB Output is correct
27 Correct 8 ms 30556 KB Output is correct
28 Correct 106 ms 71624 KB Output is correct
29 Correct 106 ms 71764 KB Output is correct
30 Correct 113 ms 71764 KB Output is correct
31 Correct 112 ms 71784 KB Output is correct
32 Correct 105 ms 71540 KB Output is correct
33 Correct 96 ms 67924 KB Output is correct
34 Correct 18 ms 34904 KB Output is correct
35 Correct 13 ms 33884 KB Output is correct
36 Correct 14 ms 33492 KB Output is correct
37 Correct 61 ms 58964 KB Output is correct
38 Correct 88 ms 65872 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 30556 KB Output is correct
2 Correct 6 ms 30652 KB Output is correct
3 Correct 5 ms 30552 KB Output is correct
4 Correct 5 ms 30296 KB Output is correct
5 Correct 5 ms 30040 KB Output is correct
6 Correct 5 ms 30416 KB Output is correct
7 Correct 5 ms 30556 KB Output is correct
8 Correct 5 ms 30552 KB Output is correct
9 Correct 5 ms 30556 KB Output is correct
10 Correct 5 ms 30660 KB Output is correct
11 Correct 5 ms 30556 KB Output is correct
12 Correct 5 ms 30556 KB Output is correct
13 Correct 5 ms 30612 KB Output is correct
14 Correct 5 ms 30556 KB Output is correct
15 Correct 5 ms 30296 KB Output is correct
16 Correct 5 ms 30556 KB Output is correct
17 Correct 5 ms 30556 KB Output is correct
18 Correct 5 ms 30556 KB Output is correct
19 Runtime error 1672 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 30556 KB Output is correct
2 Correct 6 ms 30652 KB Output is correct
3 Correct 5 ms 30552 KB Output is correct
4 Correct 5 ms 30296 KB Output is correct
5 Correct 5 ms 30040 KB Output is correct
6 Correct 5 ms 30416 KB Output is correct
7 Correct 5 ms 30556 KB Output is correct
8 Correct 5 ms 30552 KB Output is correct
9 Correct 5 ms 30556 KB Output is correct
10 Correct 5 ms 30660 KB Output is correct
11 Correct 5 ms 30556 KB Output is correct
12 Correct 5 ms 30556 KB Output is correct
13 Correct 5 ms 30612 KB Output is correct
14 Correct 5 ms 30556 KB Output is correct
15 Correct 5 ms 30296 KB Output is correct
16 Correct 5 ms 30556 KB Output is correct
17 Correct 5 ms 30556 KB Output is correct
18 Correct 5 ms 30556 KB Output is correct
19 Correct 4 ms 29988 KB Output is correct
20 Correct 5 ms 30408 KB Output is correct
21 Correct 78 ms 55144 KB Output is correct
22 Correct 9 ms 30556 KB Output is correct
23 Correct 9 ms 30500 KB Output is correct
24 Correct 9 ms 30812 KB Output is correct
25 Correct 105 ms 71688 KB Output is correct
26 Correct 15 ms 33628 KB Output is correct
27 Correct 8 ms 30556 KB Output is correct
28 Correct 106 ms 71624 KB Output is correct
29 Correct 106 ms 71764 KB Output is correct
30 Correct 113 ms 71764 KB Output is correct
31 Correct 112 ms 71784 KB Output is correct
32 Correct 105 ms 71540 KB Output is correct
33 Correct 96 ms 67924 KB Output is correct
34 Correct 18 ms 34904 KB Output is correct
35 Correct 13 ms 33884 KB Output is correct
36 Correct 14 ms 33492 KB Output is correct
37 Correct 61 ms 58964 KB Output is correct
38 Correct 88 ms 65872 KB Output is correct
39 Runtime error 1672 ms 262144 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -