Submission #1240695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240695		mychecksedad	Closing Time (IOI23_closing)	C++17	43 / 100	108 ms	56504 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long int
#define cerr if(0) cerr
const int N = 2e5+100, M = 3e5;

multiset<ll> S[N];
ll A[M], B[M], C[M], dp[N]; // 0 - 1
vector<pair<int, ll>> g[M];
vector<ll> DP[N];
bitset<M> in_path;
int sz[M];
bool dfs(int v, int p, int t, vector<int> &T){
  T.pb(v);
  if(v == t){
    return 1;
  }
  for(auto [u, w]: g[v]){
    if(u != p){
      bool ok = dfs(u, v, t, T);
      if(ok) return true;
    }
  }
  T.pop_back();
  return false;
}

void dfs2(int v, int p){
  vi U;
  sz[v] = 1;
  int big = -1;
  for(auto [u, w]: g[v]){
    if(u != p && !in_path[u]){
      dfs2(u, v);
      sz[v] += sz[u];
      U.pb(u);
      if(big == -1 || sz[big] < sz[u]) big = u;
    }
  }
  if(big == -1){
    S[v].insert(A[v]);
    return;
  }
  S[v].swap(S[big]);
  for(int u: U){
    if(u != big){
      for(ll x: S[u]) S[v].insert(x);
    }
  }
  S[v].insert(A[v]);
}

int max_score(int n, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
  for(int i = 0; i < n; ++i) g[i].clear(), S[i].clear(), DP[i].clear();
  in_path = 0;
  for(int i = 0; i < n-1; ++i){
    g[U[i]].pb({V[i], W[i]});
    g[V[i]].pb({U[i], W[i]});
  }
  vector<ll> dist(n, -1);
  dist[X] = 0;
  queue<int> q;
  q.push(X);
  while(!q.empty()){
    int v = q.front(); q.pop();
    for(auto [u, w]: g[v]){
      if(dist[u] == -1){
        dist[u] = dist[v] + w;
        q.push(u);
      }
    }
  }
  vector<ll> dist2(n, -1);
  dist2[Y] = 0;
  q.push(Y);
  while(!q.empty()){
    int v = q.front(); q.pop();
    for(auto [u, w]: g[v]){
      if(dist2[u] == -1){
        dist2[u] = dist2[v] + w;
        q.push(u);
      }
    }
  }
  for(int i = 0; i < n; ++i){
    A[i] = min(dist[i], dist2[i]);
    B[i] = max(dist[i], dist2[i]) - min(dist[i], dist2[i]);
  }
  vi T; 
  dfs(X, X, Y, T);
  for(int x: T) in_path[x] = 1;

  ll sum = 0;
  for(int x: T){
    sum += A[x];
  }

  int ans = 0;  
  ll KK = K;
  for(int j = 0; j < n; ++j) C[j] = A[j];
  
  sort(C, C+n);
  for(int j = 0; j < n; ++j){
    if(KK>= C[j]) KK-=C[j], ++ans;
  }

  if(dist[Y] > 2*K) return ans;

  for(int x: T){
    K -= A[x];
    A[x] = 0;
  }

  priority_queue<array<ll, 3>> Q;

  for(int v: T){
    dfs2(v, v);

    dp[0] = 0;
    auto it = S[v].begin();
    int cnt = 0;

    for(int i = 1; i <= sz[v]*2; ++i, ++it){
      if(it == S[v].end()){
        for(int j = i; j <= sz[v] * 2; ++j){
          dp[j] = dp[j - 1] + B[v];
        }
        break;
      }else{
        while(B[v] <= (*it) && cnt){
          --cnt;
          dp[i] = dp[i - 1] + B[v];
          ++i;
        }
        dp[i] = dp[i - 1] + (*it);
        ++cnt;
      }
    }
    for(int j = 0; j <= 2*sz[v]; ++j) DP[v].pb(dp[j]);
    Q.push({-dp[1], v, 1});
  }

  dp[0] = 0;

  int cur = 1;
  while(!Q.empty()){
    int v = Q.top()[1];
    int ptr = Q.top()[2];
    dp[cur] = dp[cur - 1] + -Q.top()[0];
    Q.pop();
    if(ptr < sz[v] * 2){
      Q.push({-(DP[v][ptr + 1] - DP[v][ptr]), v, ptr + 1});
    }
    ++cur;
  }


  for(int i = 2*n; i >= 0; --i) if(dp[i] <= K) return max(i, ans);
  return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 12
• Subtask 4: 14 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17