# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
878496 | 2023-11-24T14:21:04 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; struct Arc{int v,d;}; vector <Arc> gr[200005]; int fix[200005],dist[40000001]; int d,nd; void dfs(int u){ fix[u]=1; for (int i=0;i<(int)gr[u].size();i++){ int v=gr[u][i].v; if (!fix[v]) {nd++; d+=gr[u][i].d; dist[nd]=d; dfs(v); d-=gr[u][i].d; } } } int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { Arc tmp; for (int i=0;i<N;i++) {gr[i].clear(); fix[i]=0;} //for (int i=0;i<=2*N;i++) dist[i]=0; for (int i=0;i<N-1;i++){ tmp.v=V[i]; tmp.d=W[i]; gr[U[i]].push_back(tmp); tmp.v=U[i]; gr[V[i]].push_back(tmp); } d=0; nd=0; dist[0]=0; dfs(X); for (int i=0;i<N;i++) fix[i]=0; d=0; nd++; dist[nd]=0;dfs(Y); sort(dist,dist+nd+1); int ans=0; long long sum=0; for (int i=0;i<2*N;i++) if (sum+dist[i]>K) break; else {sum+=dist[i]; ans++; } return ans; }