Submission #1294257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294257		h1manshusingh	Race (IOI11_race)	C++20	100 / 100	986 ms	56276 KiB

race

#include "race.h"
using i64  = long long;
#include<bits/stdc++.h>
using namespace std;

int best_path(int n, int k, int H[][2], int L[])
{
      const int inf = 1e8;
      vector<vector<pair<int,int>>> G(n);
      for( int i = 0; i < n; i++){
            G[H[i][0]].push_back({H[i][1],L[i]});
            G[H[i][1]].push_back({H[i][0],L[i]});
      }
      vector<vector<int>> CG(n);
      vector<int> sz(n);
      vector<bool> visited(n);
      auto getsz = [&](auto getsz, int u, int p)->void{
            sz[u] = 1;
            for( auto [v,w]:G[u]){
                  if( v != p and !visited[v]){
                        getsz(getsz,v,u);
                        sz[u] += sz[v];
                  }
            }
      };

      auto centroid = [&](auto centroid, int u, int p, int S)->int{
            for(auto [v,w]: G[u]){
                  if( v != p and !visited[v]){
                        if( sz[v] > S/2)
                              return centroid(centroid,v,u,S);
                  }
            }
            return u;
      };
      //vector<int> K(k+1, inf);
     // vector<int> K_tmp(k+1, inf);
     map<i64,int> K;

      //auto iinf = [&](this auto && iinf, int u, int p)-void{
      //      K[u] = inf;
      //      //K_tmp = inf;
      //      for( auto [v,w]:G[u]){
      //            if( v != p and !visited[v]){
      //                  iinf(v,u);
      //            }
      //      }
      //};

     // auto iinf_temp = [&](this auto && iinf_temp, int u, int p)-void{
     //       K_tmp = inf;
     //       for( auto [v,w]:G[u]){
     //             if( v != p and !visited[v]){
     //                   iinf_temp(v,u);
     //             }
     //       }
     // };
       
      int ans = inf;

      auto find = [&](auto find, int u,int p, int d, i64 l)->void{
            if( l > k) return; // already pass the limit
            //ans = min(ans,K[k-l]+d);
            if( K.find(k-l) != K.end()){
                  ans = min( ans, K[k-l] + d);
            }
            //K_temp[l] = min(K_temp[l], d);
            for( auto [v,w]: G[u]){
                  if( v != p and !visited[v]){
                        find(find,v,u,d+1,l+w);
                  }
            }
      };
      auto optimize = [&](auto optimize, int u,int p, int d, i64 l)->void{
            if( l > k) return; // already pass the limit
            if( K.find(l) == K.end()) K[l] = d;
            else K[l] = min(K[l],d);
            for( auto [v,w]: G[u]){
                  if( v != p and !visited[v]){
                        optimize(optimize,v,u,d+1,l+w);
                  }
            }
      };

      auto decompose = [&](auto decompose, int u)->void{
            getsz(getsz,u,-1);
            int c = centroid(centroid,u,-1,sz[u]);
            visited[c] = true;
            // do the processing
            //iinf(u,-1);
            K.clear();
            K[0] = 0;
            for( auto [v,w]: G[c]){
                  if( !visited[v]){
                        // this is one component of current centroid
                        // initialise all its children to inf
                        find(find,v,c,1,w);      
                        optimize(optimize,v,c,1,w);
                        //int cent = decompose(v);
                  }
            }
            for( auto [v,w]:G[c]){
                  if( !visited[v]){
                        decompose(decompose,v);
                  }
            }
      };
      decompose(decompose,0);
      if(ans >= inf) return -1;
      return ans;
}
/*
int main(){

      const int N = 2e5+5;
      int high[N][2];
      int w[N];
      int n,k; cin >> n >> k;
      for( int i = 0; i < n-1; i++){
            cin >> high[i][0] >> high[i][1] >> w[i];
      }
      int ans = best_path(n,k,high,w);
      cout << ans << '\n';
      return 0;
}
*/

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57