Submission #1240679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240679		SalihSahin	Closing Time (IOI23_closing)	C++20	75 / 100	1188 ms	2108752 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*2+10, 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;
   long long totdis = 0;
   int make = 0;

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

      if(vis[node]) continue;
      vis[node] = 1;
      long long val = min(disx[node], disy[node]);
      
      if(val >= pathlen){
         while(make > 0){
            cnt++;
            totdis += pathlen;
            take[cnt] = totdis;
            make--;
         }
         cnt++;
         make++;
         totdis += val;
         take[cnt] = totdis;
      }
      else{
         cnt++;
         make++;
         totdis += val;
         take[cnt] = totdis;
      }


      for(auto itr: adj[node]){
         if(!vis[itr.first]){
            pq.push({-min(disx[itr.first], disy[itr.first]), itr.first});
         }
      }
   }
   while(make > 0){
      cnt++;
      totdis += pathlen;
      take[cnt] = totdis;
      make--;
   }
   for(int i = 0; i < N; i++){
      vis[i] = 0;
   }*/

   vector<int> vis(N);
   for(auto itr: path){
      vis[itr] = 1;
   }

   int M = path.size();
   vector<vector<vector<long long> > > dp(M+1, vector<vector<long long> > (4, vector<long long>(2*N+1, inf))); // 0 = bos, 1 = x, 2 = y, 3 = xy
   dp[0][1][0] = 0;
   for(int i = 0; i < M; i++){
      dp[i+1][0] = dp[i][0]; // 0 -> 0
      for(int j = 0; j <= N*2; j++){ // 1 -> 0
         dp[i+1][0][j] = min(dp[i+1][0][j], dp[i][1][j]);
      }

      for(int j = 1; j <= N*2; j++){ // 1 -> 1
         dp[i+1][1][j] = min(dp[i+1][1][j], dp[i][1][j-1] + disx[path[i]]);
      }

      for(int j = 1; j <= N*2; j++){ // 2 -> 2
         dp[i+1][2][j] = min(dp[i+1][2][j], dp[i][2][j-1] + disy[path[i]]);
      }
      for(int j = 1; j <= N*2; j++){ // 1 -> 2
         dp[i+1][2][j] = min(dp[i+1][2][j], dp[i][1][j-1] + disy[path[i]]);
      }
      for(int j = 1; j <= N*2; j++){ // 3 -> 2
         dp[i+1][2][j] = min(dp[i+1][2][j], dp[i][3][j-1] + disy[path[i]]);
      }
      for(int j = 1; j <= N*2; j++){ // 0 -> 2
         dp[i+1][2][j] = min(dp[i+1][2][j], dp[i][0][j-1] + disy[path[i]]);
      }

      for(int j = 2; j <= N*2; j++){ // 3 -> 3
         dp[i+1][3][j] = min(dp[i+1][3][j], dp[i][3][j-2] + max(disx[path[i]], disy[path[i]]));
      }
      for(int j = 2; j <= N*2; j++){ // 1 -> 3
         dp[i+1][3][j] = min(dp[i+1][3][j], dp[i][1][j-2] + max(disx[path[i]], disy[path[i]]));
      }

      // düz transitionlarım bitti şimdi 0 hariç caseine göre dp yapıp transition atcaz

      for(int j = 0; j < N; j++){
         vis[j] = 0;
      }
      for(auto itr: path){
         vis[itr] = 1;
      }

      vector<long long> dpin(N*2+1, inf); // 1in dpsi
      dpin[0] = 0;
      priority_queue<pair<long long, long long> > pq;
      for(auto itr: adj[path[i]]){
         pq.push({-disx[itr.first], itr.first});
      }
      long long df = abs(disx[path[i]] - disy[path[i]]);

      int cnt = 0, make = 0;
      long long totdis = 0;

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

         if(vis[node]) continue;
         vis[node] = 1;
         long long val = disx[node];
         cnt++;
         totdis += val;
         dpin[cnt] = totdis;


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

      for(int l = N*2; l >= 0; l--){
         for(int j = 0; j <= l; j++){
            if(dpin[j] == inf) break;
            dp[i+1][1][l] = min(dp[i+1][1][l], dp[i+1][1][l-j] + dpin[j]);
         }
      }

      for(int j = 0; j < N; j++){
         vis[j] = 0;
      }
      for(auto itr: path){
         vis[itr] = 1;
      }

      //vector<long long> dpin(N*2+1, inf); // 1in dpsi
      dpin.assign(N*2+1, inf);
      dpin[0] = 0;
      //priority_queue<pair<long long, long long> > pq;
      for(auto itr: adj[path[i]]){
         pq.push({-disy[itr.first], itr.first});
      }

      cnt = 0, make = 0;
      totdis = 0;

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

         if(vis[node]) continue;
         vis[node] = 1;
         long long val = disy[node];
         cnt++;
         totdis += val;
         dpin[cnt] = totdis;


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

      for(int l = N*2; l >= 0; l--){
         for(int j = 0; j <= l; j++){
            if(dpin[j] == inf) break;
            dp[i+1][2][l] = min(dp[i+1][2][l], dp[i+1][2][l-j] + dpin[j]);
         }
      }

      for(int j = 0; j < N; j++){
         vis[j] = 0;
      }
      for(auto itr: path){
         vis[itr] = 1;
      }

      //vector<long long> dpin(N*2+1, inf); // 1in dpsi
      dpin.assign(N*2+1, inf);
      dpin[0] = 0;
      //priority_queue<pair<long long, long long> > pq;
      for(auto itr: adj[path[i]]){
         pq.push({-min(disy[itr.first], disx[itr.first]), itr.first});
      }

      cnt = 0, make = 0;
      totdis = 0;

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

         if(vis[node]) continue;
         vis[node] = 1;
         long long val = min(disx[node], disy[node]);
         
         if(val >= df){
            while(make > 0){
               cnt++;
               totdis += df;
               dpin[cnt] = totdis;
               make--;
            }
            cnt++;
            make++;
            totdis += val;
            dpin[cnt] = totdis;
         }
         else{
            cnt++;
            make++;
            totdis += val;
            dpin[cnt] = totdis;
         }

         for(auto itr: adj[node]){
            if(!vis[itr.first]){
               pq.push({-min(disx[itr.first], disy[itr.first]), itr.first});
            }
         }
      }
      while(make > 0){
         cnt++;
         totdis += df;
         dpin[cnt] = totdis;
         make--;
      }

      for(int l = N*2; l >= 0; l--){
         for(int j = 0; j <= l; j++){
            if(dpin[j] == inf) break;
            dp[i+1][3][l] = min(dp[i+1][3][l], dp[i+1][3][l-j] + dpin[j]);
         }
      }

      /*
      cout<<"index : "<<i+1<<endl;
      for(int j = 0; j < 4; j++){
         for(int take = 0; take <= N*2; take++){
            cout<<j<<" "<<take<<" -> "<<dp[i+1][j][take]<<" "<<endl;
         }
         cout<<endl;
      }*/
   }

   int ans = 0;
   for(int i = 2; i < 4; i++){
      for(int j = 0; j <= N*2; j++){
         if(dp[M][i][j] <= K) ans = max(ans, j);
      }
   }

   return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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: 0 / 17