Submission #1240507

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240507		SalihSahin	Closing Time (IOI23_closing)	C++20	21 / 100	1098 ms	31408 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);

   reverse(path.begin(), path.end());
   path.pb(X);
   reverse(path.begin(), path.end()); // X ..... Y
   long long pathlen = disx[Y];

   vector<long long> take(N+1, inf);
   take[0] = 0;

   priority_queue<pair<long long, long long> > pq;
   vector<int> vis(N);
   for(auto itr: path){
      vis[itr] = 1;
   }
   for(auto itr: adj[X]){
      pq.push({-disx[itr.first], itr.first});
   }
   for(auto itr: adj[Y]){
      pq.push({-disy[itr.first], itr.first});
   }

   int cnt = 0, ind = -1;
   long long totdis = 0;

   while(!pq.empty()){
      int node = pq.top().second;
      pq.pop();

      if(vis[node]) continue;
      vis[node] = 1;
      cnt++;
      long long val = min(disx[node], disy[node]);
      totdis += val; 
      if(val >= pathlen && ind == -1){ // i degerim >= ind ise pathlen almak daha optimal
         ind = cnt;
      }

      take[cnt] = totdis;

      for(auto itr: adj[node]){
         if(!vis[itr.first]){
            pq.push({-min(disx[itr.first], disy[itr.first]), itr.first});
         }
      }
   }

   for(int i = 0; i < N; i++){
      vis[i] = 0;
   }

   int ans = 0;
   vector<long long> pre(path.size());
   for(int i = 1; i < path.size(); i++){
      pre[i] = pre[i-1] + disx[path[i]];
   }

   vector<long long> suf(path.size());
   for(int i = path.size()-2; i >= 0; i--){
      suf[i] = suf[i+1] + disy[path[i]];
   }

   vector<long long> cik(path.size()+1);
   for(int i = 0; i < path.size(); i++){
      cik[i+1] = cik[i] - min(disx[path[i]], disy[path[i]]);
   }


   for(int xr = 0; xr < path.size(); xr++){
      for(int yl = 0; yl < path.size(); yl++){
         long long discalc;
         if(xr < yl){
            discalc = pre[xr] + suf[yl];
         }
         else{
            discalc = pre[xr] + suf[yl] + (cik[xr+1] - cik[yl]);
         }

         int anscalc = (xr + 1) + (path.size() - yl);
         if(discalc > K) continue;

         for(int i = 0; i < N; i++){
            long long dishere = discalc + take[i];
            if(dishere > K) break;

            long long add = min((long long)i, (K - dishere) / pathlen);
            int anshere = anscalc + i + add;
            ans = max(ans, anshere);
            //cout<<xr<<" "<<yl<<" "<<i<<" üclüsü icin best = "<<anshere<<endl;
         }
      }
   }

   return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 9 / 9
• Subtask 3: 12 / 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