Submission #1176304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176304		pera	Race (IOI11_race)	C++20	100 / 100	260 ms	34296 KiB

race

#include<bits/stdc++.h>
using namespace std;
const int N = 2E5 + 1 , M = 1E6 + 1;
vector<int> dead(N) , sz(N) , f(M , -1);
vector<pair<int , int>> g[N];
int gsz(int u , int p = 0){
   int s = 0;
   for(auto [v , w] : g[u]){
      if(v != p && !dead[v]){
         s += gsz(v , u);
      }
   }
   sz[u] = ++s;
   return sz[u];
}
int find(int u , int m , int p = 0){
   for(auto [v , w] : g[u]){
      if(v != p && !dead[v] && sz[v] > m / 2){
         return find(v , m , u);
      }
   }
   return u;
}
void calc(int u , int p , int D , int L , int K , vector<pair<int , int>> &d){
   if(L > K){
      return;
   }
   d.emplace_back(L , D);
   ++D;
   for(auto [v , w] : g[u]){
      if(v != p && !dead[v]){
         calc(v , u , D , L + w , K , d);
      }
   }
}
int solve(int u , int k){
   u = find(u , gsz(u));
   int ans = 1E9;
   f[0] = 0;
   vector<int> clr;
   for(auto [v , w] : g[u]){
      if(!dead[v]){
         vector<pair<int , int>> dists;
         calc(v , u , 1 , w , k , dists);
         for(auto [X , Y] : dists){
            if(f[k - X] != -1){
               ans = min(ans , Y + f[k - X]);
            }
         }
         for(auto [X , Y] : dists){
            if(f[X] == -1){
               f[X] = Y;
            }else{
               f[X] = min(f[X] , Y);
            }
            clr.emplace_back(X);
         }
      }
   }
   for(int x : clr){
      f[x] = -1;
   }
   dead[u] = 1;
   for(auto [v , w] : g[u]){
      if(!dead[v]){
         ans = min(ans , solve(v , k));
      }
   }
   return ans;
}
int best_path(int N, int K, int H[][2], int L[]){
   for(int i = 0;i < N - 1;i ++){
      for(int w = 0;w < 2;w ++){
         ++H[i][w];
      }
      for(int w = 0;w < 2;w ++){
         g[H[i][w]].emplace_back(H[i][w ^ 1] , L[i]);
      }
   }
   int A = solve(1 , K);
   if(A > N){
      A = -1;
   }
   return A;
}

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