Submission #1233346

#TimeUsernameProblemLanguageResultExecution timeMemory
1233346MuhammadSaramClosing Time (IOI23_closing)C++20
8 / 100
143 ms22964 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define ff first #define ss second const int M = 2e5 + 1; const ll inf = 1e18; ll dis[M]; vector<pair<int,int>> nei[M]; void dijkstra(int u) { set<pair<ll,int>> se; dis[u]=0; se.insert({0,u}); while (!se.empty()) { auto p=*se.begin();se.erase(p); for (auto [i,w]:nei[p.second]) if (dis[i]>p.first+w) { se.erase({dis[i],i}); dis[i]=p.first+w; se.insert({dis[i],i}); } } } 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++) nei[i].clear(); for (int i=0;i<n-1;i++) nei[u[i]].push_back({v[i],w[i]}), nei[v[i]].push_back({u[i],w[i]}); for (int i=0;i<n;i++) dis[i]=inf; dijkstra(x); vector<ll> a; for (int i=0;i<n;i++) a.push_back(dis[i]); for (int i=0;i<n;i++) dis[i]=inf; dijkstra(y); for (int i=0;i<n;i++) a.push_back(dis[i]); sort(a.begin(),a.end()); int ans=0; for (int i=0;i<a.size();i++) if (a[i]>k) break; else ans++,k-=a[i]; 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...