Submission #938809

#	Time	Username	Problem	Language	Result	Execution time	Memory
938809		duckindog	경주 (Race) (IOI11_race)	C++17	0 / 100	3 ms	9820 KiB

race

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
#ifndef LOCAL
#include "race.h"
#endif
 
const int N = 200'000 + 1;
vector<pair<int, int>> ad[N];
 
// namespace sub2 {
//   long long d[N], dep[N];
//   int f[N][10], st[N], ed[N], it;
//   void dfs(int u, int pre = 0) { 
//     st[u] = ++it;
//     for (int i = 1; i <= 9; ++i)
//       f[u][i] = f[f[u][i - 1]][i - 1];
 
//     for (const auto& [v, w] : ad[u]) { 
//       if (v == pre) continue;
//       d[v] = d[u] + w;
//       dep[v] = dep[u] + 1;
//       f[v][0] = u;
//       dfs(v, u);
//     }
//     ed[u] = it;
//   }
//   bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }
//   int lca(int u, int v) { 
//     if (anc(u, v)) return u;
//     if (anc(v, u)) return v;
 
//     for (int i = 9; i >= 0; --i)
//       if (!anc(f[u][i], v)) u = f[u][i];
//     return f[u][0];
//   }
 
//   int solve(int n, int k) { 
//     dfs(0);
//     long long answer = 1e7;
//     for (int i = 0; i < n; ++i) { 
//       for (int j = i + 1; j < n; ++j) { 
//         int l = lca(i, j);
//         int distant = d[i] + d[j] - 2 * d[l];
//         if (distant == k) answer = min(answer, dep[i] + dep[j] - 2 * dep[l]);
//       }
//     }
 
//     return answer == 1e7 ? -1 : answer; 
//   }
 
// }
 
namespace sub3 {
  int dpin[N][101];
  int n, k;
  void dfs1(int u, int pre = 0) { 
    dpin[u][0] = 0;
    for (const auto& [v, w] : ad[u]) { 
      if (v == pre) continue;
      dfs1(v, u);
      for (int i = 1; i <= k; ++i) if (i - w >= 0) dpin[u][i] = min(dpin[u][i], dpin[v][i - w] + 1);
    }
  }
  
  int answer;
  void dfs2(int u, int pre = 0) { 
    if (!u) answer = 1e7;
    
    vector<array<pair<int, int>, 2>> best(k + 1);
    for (int i = 0; i <= k; ++i) best[i][0] = best[i][1] = {1e7, -1};
    auto add = [&](int i, pair<int, int> val) { 
      if (best[i][1] > val) swap(best[i][1], val);
      if (best[i][0] > best[i][1]) swap(best[i][0], best[i][1]);
      if (best[i][1] > val) swap(best[i][1], val);
    };

    for (const auto&[v, w] : ad[u]) { 
      if (v == pre) continue;
      for (int i = 0; i <= k; ++i) if (i - w >= 0) add(i, {dpin[v][i - w], v});
    }
    
    for (const auto&[v, w] : ad[u]) { 
      if (v == pre || k - w < 0) continue;
      for (int i = 0; i <= k; ++i) { 
        int preW = k - i - w;
        if (preW < 0) continue;
        int val = (best[preW][0].second == v ? best[preW][1].first : best[i][0].first);
        answer = min(answer, val + dpin[v][i]);
      }
      best.clear();
      dfs2(v, u);
    }
  }
 
  int solve(int a, int b) { 
    n = a; k = b;
    memset(dpin, 63, sizeof dpin);

    
    dfs1(0); dfs2(0);
    for (int i = 0; i <= n; ++i) answer = min(answer, dpin[i][k]);
    
    return (answer > n ? -1 : answer);
  }
 
}
 
int best_path(int n, int k, int h[][2], int l[]) { 
  for (int i = 0; i < n - 1; ++i) { 
    int u = h[i][0], v = h[i][1], w = l[i];
    if (u > v) swap(u, v);
    ad[u].push_back({v, w});
    ad[v].push_back({u, w});
  }
  int sub = (n <= 1000 ? 2 : k <= 100 ? 3 : 4);
  // if (sub == 2) return sub2::solve(n, k);
  if (sub == 3) return sub3::solve(n, k);
  return -1;
} 
 
#ifdef LOCAL
#define MAX_AA 500000
static int AA, K;
static int H[MAX_AA][2];
static int L[MAX_AA];
static int solution;
 
#define int long long
mt19937_64 rng(8384815663);
int rnd(int l, int r) { return l + rng() % (r - l + 1); }
 
inline 
void my_assert(int e) {if (!e) abort();}
 
void read_input()
{
  AA = rnd(2e5, 2e5), K = rnd(100, 100);
  // cin >> AA >> K;
  for (int i = 0; i < AA - 1; ++i) { 
    H[i][0] = rnd(i, i);
    H[i][1] = i + 1;
    L[i] = rnd(1, 100);
    // cin >> H[i][0] >> H[i][1] >> L[i];
  }
  solution = -1;
  // cin >> solution;
}
 
int32_t main() {
  int ans;
  read_input();
  ans = best_path(AA,K,H,L);
  cout << ans << "\n";
 
  return 0;
}
#endif

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