oj.uz

Submission #1064647

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

vector<pair<ll,ll>> adj[200001];
ll sz[200001];
bool marked[200001]={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!=v&&!marked[v]&&sz[v]>=(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 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10576 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 11096 KB Output is correct
9 Correct 4 ms 10896 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10576 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 11096 KB Output is correct
9 Correct 4 ms 10896 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Incorrect 2 ms 10584 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10576 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 11096 KB Output is correct
9 Correct 4 ms 10896 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 368 ms 30144 KB Output is correct
20 Correct 374 ms 31568 KB Output is correct
21 Correct 281 ms 27104 KB Output is correct
22 Correct 215 ms 31028 KB Output is correct
23 Incorrect 348 ms 41144 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10576 KB Output is correct
5 Correct 2 ms 10332 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 11096 KB Output is correct
9 Correct 4 ms 10896 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 2 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Incorrect 2 ms 10584 KB Output isn't correct
20 Halted 0 ms 0 KB -