Submission #651446

#	Time	Username	Problem	Language	Result	Execution time	Memory
651446		pauloamed	Race (IOI11_race)	C++17	9 / 100	320 ms	18616 KiB

race

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

#define ll long long

const int MAXN = 200000;

vector<pair<int,int>> v[MAXN];

map<ll,multiset<int>> w2e;
int get(ll h){
  return *w2e[h].begin();
}
void erase(ll h, int x){
  w2e[h].erase(w2e[h].find(x));
  if(w2e[h].size() == 0) w2e.erase(h);
}
void add(ll h, int x){
  w2e[h].insert(x);
}

int k, ans;

namespace sack{
  int T;
  int t_in[MAXN], t_out[MAXN], t2node[MAXN];
  int sz[MAXN];

  int depth[MAXN];
  ll wdepth[MAXN];

  void precalc(int x, int par=-1, int d=0, int dw=0){
    t2node[T] = x; t_in[x] = T++; sz[x] = 1;
    
    depth[x] = d, wdepth[x] = dw;
    for(auto [y, w] : v[x]) if(y != par) {
      precalc(y, x, d + 1, dw + w);
      sz[x] += sz[y];
    }
    t_out[x] = T;
  }

  void solve(int x, int par=-1, bool keep=0){
    int hc = -1; // heavy_child
    for(auto [y, w] : v[x]) if(y != par) {
      if(hc == -1 || sz[y] > sz[hc]) hc = y;
    }

    if(hc != -1){
      // solve but dont keep light nodes
      for(auto [y, w] : v[x]) if(y != par && y != hc)
        solve(y, x, false);
      // solve and keep heavy nodes
      solve(hc, x, true);
    }

    for(auto [y, w] : v[x]) if(y != par && y != hc) {
      // maybe solve queries (light -> (heavy + past_lights))
      for(int t = t_in[y]; t < t_out[y]; ++t){
        int z = t2node[t];
        // query z
        ll goal = wdepth[x] * 2 + k;
        ll missing = goal - wdepth[z];
        int my_edges = depth[z] - depth[x];

        if(w2e.count(missing)){
          int friend_edges = get(missing);
          ans = min(ans, my_edges + friend_edges);
        }
      }
      // add light nodes after solving, avoid info leakage
      for(int t = t_in[y]; t < t_out[y]; ++t){
        int z = t2node[t];
        // add z
        add(wdepth[z], depth[z]);
      }
    }
  
    // solve queries (x -> all subtrees)
    if(w2e.count(wdepth[x] + k)){
      ans = min(ans, get(wdepth[x] + k) - depth[x]);
    }

    // add x for querying or for keeping as heavy child
    add(wdepth[x], depth[x]);

    if(!keep){
      for(int t = t_in[x]; t < t_out[x]; ++t){
        int z = t2node[t];
        // rmv z
        erase(wdepth[z], depth[z]);
      }
    }
  }
}

int best_path(int N, int K, int H[][2], int L[]){
  for(int i = 0; i < N; ++i) v[i].clear();

  for(int i = 0; i + 1 < N; ++i){
    int a = H[i][0], b = H[i][1];
    int c = L[i];
    v[a].push_back({b, c});
    v[b].push_back({a, c});
  }
  ans = INT_MAX;
  k = K;

  sack::precalc(0);
  sack::solve(0);

  if(ans == INT_MAX) return -1;
  else return ans;
}

// int32_t main(){
//   int n, k; cin >> n >> k;
//   int h[n-1][2];
//   int l[n-1];
//   for(int i = 0; i < n-1; ++i){
//     cin >> h[i][0] >> h[i][1] >> l[i];
//   }
//   cout << best_path(n, k, h, l);

//   int x; cin >> x;
//   cout << " " << x << "\n";
// }

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