Submission #1166799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166799		kim	Closing Time (IOI23_closing)	C++20	8 / 100	59 ms	21832 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()
#define add(x,y) ((x+y)%md)
#define Add(x,y) (x=add(x,y))
#define mul(x,y) ((x*y)%md)
#define Mul(x,y) (x=mul(x,y))
const int inf=1e9;
const ll linf=1e18;
const ll md=1e9+7;

vector<pair<int,ll>> adj[200005];

using A=tuple<ll,int,int,ll>;
priority_queue<A,vector<A>,greater<A>> pq;
ll a[200005];

int dfs(int u,int p){
  int res=1;
  for(auto &[v,vw]:adj[u]) if(v!=p && vw<=a[v]) res+=dfs(v,u);
  return res;
}

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) adj[i].clear(), a[i]=0;
  for(int i=0;i<N-1;++i) adj[U[i]].eb(V[i],W[i]), adj[V[i]].eb(U[i],W[i]);
  pq.emplace(0,X,-1,0), pq.emplace(0,Y,-1,0);
  ll sum=0;
  while(!pq.empty()){
    auto [w,u,p,w0]=pq.top(); pq.pop();
    if(w!=max(0LL,w0-a[u])){
      pq.emplace(max(0LL,w0-a[u]),u,p,w0);
      continue;
    }
    if(sum+w>K) continue;
    sum+=w;
    a[u]+=w;
    for(auto &[v,vw]:adj[u]) if(v!=p){
      pq.emplace(max(0LL,vw+w0-a[v]),v,u,vw+w0);
    }
  }
  return dfs(X,-1)+dfs(Y,-1);
}

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