Submission #1240541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240541		SalihSahin	Closing Time (IOI23_closing)	C++20	8 / 100	89 ms	36672 KiB

closing

#include "bits/stdc++.h"
#include "closing.h"
#define pb push_back
using namespace std;

const long long inf = 1e18 + 5;
const int MAXN = 2e5 + 5;

vector<int> curpath, path;
vector<long long> disx(MAXN), disy(MAXN);
vector<pair<int, int> > adj[MAXN];

void dfs(int node, int par, int target){
   if(node == target){
      path = curpath;
   }

   for(auto itr: adj[node]){
      if(itr.first != par){
         curpath.pb(itr.first);
         dfs(itr.first, node, target);
         curpath.pop_back();
      }
   }
}

void disc(int node, int par, long long dis, int type){
   if(!type) disx[node] = dis;
   else disy[node] = dis;

   for(auto itr: adj[node]){
      if(itr.first != par){
         disc(itr.first, node, dis + itr.second, type);
      }
   }
}

int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){
   for(int i = 0; i < N; i++){
      adj[i].clear();
   }
   for(int i = 0; i < N-1; i++){
      adj[U[i]].pb({V[i], W[i]});
      adj[V[i]].pb({U[i], W[i]});
   }

   disc(X, X, 0, 0);
   disc(Y, Y, 0, 1);

   curpath.clear();
   path.clear();
   dfs(X, X, Y);

   priority_queue<long long> pq;
   for(int i = 0; i < N; i++){
      pq.push({-min(disx[i], disy[i])});
   }
   int ans = 0;
   long long cur = 0;
   while(!pq.empty()){
      long long val = pq.top() * (-1);
      pq.pop();

      if(val + cur <= K){
         cur += val;
         ans++;
      }
      else break;
   }

   return ans;
}

• 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