Submission #878483

#TimeUsernameProblemLanguageResultExecution timeMemory
878483gurkotClosing Time (IOI23_closing)C++17
0 / 100
81 ms27216 KiB
#include <vector> #include <algorithm> using namespace std; struct Arc{int v,d;}; vector<Arc> gr[200000]; long long dist[400001]; long long d; int nd; bool fix[200000]; 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=1;i<N;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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...