/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 5ms 5.02 MiB
#2 Accepted 5ms 5.02 MiB
#3 Accepted 5ms 5.246 MiB
#4 Accepted 5ms 5.02 MiB
#5 Time Exceeded ≥2123ms ≥348.348 MiB
#6 Time Exceeded ≥2119ms ≥319.078 MiB

Code

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

typedef long long ll;
const int MAXN = 200005;
const int MAXK = 105;

vector<int> g[MAXN];
ll dp[MAXN][MAXK], dp2[MAXN][MAXK];
int N, K;

void dfs(int u, int p) {
  for (int v : g[u]) {
    if (v == p) continue;
    dfs(v, u);
  }

  dp2[u][0] = 1;
  dp[u][0] = 1;
  for (int v : g[u]) {
    if (v == p) continue;
    dp[u][0] = max(dp[u][0], 1 + dp[v][0]);
  }

  for (int j = 1; j <= K; ++j) {
    // dp2[u][j]: path ending at u after j backs
    ll best = 0;
    for (int v : g[u]) {
      if (v == p) continue;
      best = max(best, dp2[v][j - 1]);
    }
    dp2[u][j] = 1 + best;

    // dp[u][j]: unconstrained
    dp[u][j] = dp2[u][j];
    for (int v : g[u]) {
      if (v == p) continue;
      dp[u][j] = max(dp[u][j], 1 + dp[v][j]);
    }

    // merging
    vector<multiset<ll>> val(j);
    for (int v : g[u]) {
      if (v == p) continue;
      for (int rem = 0; rem <= j - 1; ++rem) {
        val[rem].insert(dp[v][rem]);
      }
    }

    for (int v : g[u]) {
      if (v == p) continue;
      for (int x = 0; x <= j - 1; ++x) {
        ll left = dp2[v][x];
        ll rem = j - 1 - x;
        if (rem < 0) continue;

        val[rem].erase(val[rem].find(dp[v][rem]));

        if (!val[rem].empty()) {
          ll right = *val[rem].rbegin();
          dp[u][j] = max(dp[u][j], 1 + left + right);
        }

        val[rem].insert(dp[v][rem]);
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N >> K;
  for (int i = 1; i < N; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  dfs(1, 0);

  ll ans = 0;
  for (int j = 0; j <= K; ++j) {
    ans = max(ans, dp[1][j]);
  }

  cout << ans << '\n';
}

Information

Submit By
Type
Submission
Problem
P1111 G. Thakurs tree game
Language
C++17 (G++ 13.2.0)
Submit At
2025-07-15 21:49:05
Judged At
2025-07-15 21:49:05
Judged By
Score
15
Total Time
≥2123ms
Peak Memory
≥348.348 MiB