Submission #1194375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194375		Ak_16	Closing Time (IOI23_closing)	C++20	75 / 100	186 ms	141948 KiB

closing

#include <iostream>
#include <vector>
#include "closing.h"
#include <algorithm>
using namespace std;
#define ll long long

struct edg{
  int no;
  ll len;
};

int tot1;
int tot2;
vector<edg> adj[5000];
ll disa[5000];
ll disb[5000];
int vis[5000];

ll dp[3005][6005];
ll cos1[5000];
ll cos2[5000];
ll ne[5000];
ll sm;

void dfs1(int nod, ll di){
  vis[nod] = 1;
  disa[nod] = di;
  for(auto edge : adj[nod]){
    int n1 = edge.no;
    int n2 = edge.len;
    if(vis[n1]==0){
      dfs1(n1, di+n2);
    }
  }
  
}

void dfs2(int nod, ll di){
  vis[nod] = 1;
  disb[nod] = di;
  for(auto edge : adj[nod]){
    int n1 = edge.no;
    int n2 = edge.len;
    if(vis[n1]==0){
      dfs2(n1, di+n2);
    }
  }
  
}



int max_score(int n, int x, int y, ll 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]].emplace_back(edg{v[i],1LL * w[i]});
    adj[v[i]].emplace_back(edg{u[i],1LL * w[i]});
  }
  
  for(int i=0; i<n; i++){
    vis[i]=0;
    disa[i]=0LL;
    disb[i]=0LL;
  }
  
  dfs1(x, 0LL);
  
  for(int i=0; i<n; i++){
    vis[i]=0;
  }
  
  dfs2(y,0LL);
  
  for(int i=0; i<n; i++){
    cos1[i] = min(disa[i], disb[i]);
    cos2[i] = max(disa[i], disb[i]);
  }
  
  for(int i=0; i<n; i++){
    ne[i] = cos1[i];
  }
  
  sort(ne, ne+n);
  

  tot1=0;
  
  sm=0LL;
  for(int i=0; i<n; i++){
    if(sm+ne[i]<=k){
      sm += ne[i]; tot1++;
    }
  }
  
  tot2=0;
  
  for(int i=0; i<=n; i++){
    for(int j=0; j<=2*n; j++){
      dp[i][j] = k+1;
    }
  }
  
  dp[0][0]=0;
  
  for(int i=0; i<n; i++){
    
    for(int j=0; j<=2*i; j++){
      dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + cos1[i]);
      dp[i+1][j+2] = min(dp[i+1][j+2], dp[i][j] + cos2[i]);
      
      if(disa[i]+disb[i]>disa[y]){
        dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
        
      }
    }
    
  }
  
  for(int i=1; i<=2*n; i++){
    if(dp[n][i]<=k){
      tot2 = i;
    }
  }
  
  return max(tot1, tot2);
  
}

• 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