Submission #939900

#	Time	Username	Problem	Language	Result	Execution time	Memory
939900		AdamGS	Closing Time (IOI23_closing)	C++17	100 / 100	163 ms	53700 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=2e5+7;
vector<pair<ll,ll>>V[LIM];
ll odl[LIM][2], czy[LIM], ile[LIM], n;
void DFS(int x, int o, int k) {
  for(auto i : V[x]) if(i.st!=o) {
    odl[i.st][k]=odl[x][k]+i.nd;
    DFS(i.st, x, k);
  }
}
void DFS2(int x, int o) {
  for(auto i : V[x]) if(i.st!=o) {
    DFS2(i.st, x);
    if(czy[i.st]) czy[x]=1;
  }
}
int max_score(int _N, int x, int y, ll k, vector<int>_U, vector<int>_V, vector<int>_W) {
  n=_N;
  rep(i, n) {
    V[i].clear();
    odl[i][0]=odl[i][1]=czy[i]=ile[i]=0;
  }
  rep(i, n-1) {
    V[_U[i]].pb({_V[i], _W[i]});
    V[_V[i]].pb({_U[i], _W[i]});
  }
  DFS(x, x, 0);
  DFS(y, y, 1);
  vector<ll>P;
  ll sum1=0, sum2=0;
  int ans1=0, ans2=0;
  rep(i, n) {
    if(odl[i][0]>odl[i][1]) swap(odl[i][0], odl[i][1]);
    odl[i][1]-=odl[i][0];
    P.pb(odl[i][0]);
  }
  sort(all(P));
  for(auto i : P) if(sum1+i<=k) {
    sum1+=i;
    ++ans1;
  }
  czy[y]=1;
  DFS2(x, x);
  vector<pair<pair<ll,ll>,ll>>S;
  rep(i, n) {
    if(czy[i]) {
      sum2+=odl[i][0];
      ile[i]=1;
      ++ans2;
      S.pb({{2*odl[i][1], 1}, i});
    } else if(odl[i][0]>=odl[i][1]) S.pb({{odl[i][0]+odl[i][1], 2}, i});
    else {
      S.pb({{2*odl[i][0], 1}, i});
      S.pb({{2*odl[i][1], 1}, i});
    }
  }
  if(sum2>k) return ans1;
  sort(all(S));
  for(auto i : S) if(sum2+i.st.st*i.st.nd/2<=k) {
    sum2+=i.st.st*i.st.nd/2;
    ans2+=i.st.nd;
    ile[i.nd]+=i.st.nd;
  }
  if(ans1>ans2) return ans1;
  rep(i, n) {
    if(ile[i]==0) {
      if(sum2+odl[i][0]<=k) return ans2+1;
    } else if(ile[i]==1) {
      if(sum2+odl[i][1]<=k) return ans2+1;
    }
  }
  ll dwa=INF;
  rep(i, n) if(ile[i]==0) dwa=min(dwa, odl[i][0]+odl[i][1]);
  rep(i, n) if(ile[i]==2 && sum2-odl[i][1]+dwa<=k) return ans2+1;
  rep(i, n) if(!czy[i] && ile[i]==1 && sum2-odl[i][0]+dwa<=k) return ans2+1;
  return ans2;
}

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