# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
878489 | 2023-11-24T14:16:21 Z | Sandro123 | Closing Time (IOI23_closing) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> #define pb push_back #define int long long #define f first #define s second using namespace std; const int P=2*1e6+5; vector <pair <int,int> > gr[P]; int fix[P],dist[2*P]; int d,nd; void dfs(int x){ fix[x]=1; for(int i=0; i<(int)gr[x].size(); i++){ int v=gr[x][i].f; if(fix[v]==0){ nd++; d+=gr[x][i].s; dist[nd]=d; dfs(v); d-=gr[x][i].s; } } } 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++){ fix[i]=0; gr[i].clear(); } for(int i=0; i<2*N; i++){ dist[i]=0; } for(int i=1; i<N; i++){ gr[U[i]].pb({V[i],W[i]}); gr[V[i]].pb({U[i],W[i]}); } d=0; nd=0; dist[0]=0; dfs(X); for(int i=0; i<N; i++){ fix[i]=0; } nd++; d=0; dist[nd]=0; dfs(Y); sort(dist,dist+nd+1); int sm=0,ans=0; for(int i=0; i<2*N; i++){ if(sm+dist[i]>K){ break; } sm+=dist[i]; ans++; } return ans; }