oj.uz

Submission #1065840

# Submission time Handle Problem Language Result Execution time Memory
1065840 2024-08-19T12:16:20 Z Hugo1729 Race (IOI11_race) C++11
0 / 100
 3 ms 4956 KB 
#include <bits/stdc++.h>
#include "race.h"

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,fma,sse,sse2,sse4")


using namespace std;
typedef long long ll;


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

int m[1000001];
 
int k;
 
int dfs_sizes(int v, int pV){
    sz[v]=1;
    for(auto [w,d] : adj[v]){
        if(w!=pV&&!marked[w]){
            sz[v]+=dfs_sizes(w,v);
        }
    }
    return sz[v];
}
 
int dfs_centroid(int v, int pV, int 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(int v, int pV,int dist,int l, vector<pair<int,int>> &a){
    for(auto [w,d] : adj[v]){
        if(w!=pV&&!marked[w]){
            if(dist+d<=k){
                a.push_back({dist+d,l+1});
                dfs_paths(w,v,dist+d,l+1,a);
            }
        }
    }
}
 
 
int centroid_decomposition(int v){
    int c = dfs_centroid(v,v,dfs_sizes(v,v));
 
 
    marked[c]=1;
    
    int ans=1000001;

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

            dfs_paths(w,c,d,1,a);
 
            for(auto [dist,l] : a){
                if(m[k-dist]!=1000001){
                    ans=min(ans,l+m[k-dist]);
                }
            }
            for(auto [dist,l] : a){
                if(m[dist]!=1000001)m[dist]=min(m[dist],l);
                else{
                    m[dist]=l;
                    sus.push_back(dist);
                }
            }
        }
    }

    for(int i : sus)m[i]=1000001;

    for(auto [w,d] : adj[c]){
        if(!marked[w]){
            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;

    for(int i=0;i<=k;i++)m[i]=1000001;
    m[0]=0;

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

Compilation message

race.cpp: In function 'int dfs_sizes(int, int)':
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 'int dfs_centroid(int, int, 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 'void dfs_paths(int, int, int, int, std::vector<std::pair<int, int> >&)':
race.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto [w,d] : adj[v]){
      |              ^
race.cpp: In function 'int centroid_decomposition(int)':
race.cpp:62:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for(auto [w,d] : adj[c]){
      |              ^
race.cpp:68:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |             for(auto [dist,l] : a){
      |                      ^
race.cpp:73:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |             for(auto [dist,l] : a){
      |                      ^
race.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |     for(auto [w,d] : adj[c]){
      |              ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4932 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Incorrect 2 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4932 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Incorrect 2 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4932 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Incorrect 2 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4932 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4956 KB Output is correct
5 Correct 3 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Incorrect 2 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -