Submission #1160500

#TimeUsernameProblemLanguageResultExecution timeMemory
1160500kl0989eClosing Time (IOI23_closing)C++20
100 / 100
348 ms56876 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pi pair<int, int> #define pl pair<ll, ll> #define vi vector<int> #define vl vector<ll> #define fi first #define se second #define pb push_back #define all(x) (x).begin(),(x).end() const int maxn=2e5+10; vector<vector<pi>> graph(maxn); vl vala(maxn,0); vl valb(maxn,0); void dfs(int cur, int prev=-1, ll dist=0) { vala[cur]=dist; for (auto [to,add]:graph[cur]) { if (to!=prev) { dfs(to,cur,dist+add); } } } int max_score(int n, int x, int y, long long k, vi u, vi v, vi w) { for (int i=0; i<n; i++) { graph[i].clear(); vala[i]=valb[i]=0; } for (int i=0; i<n-1; i++) { graph[u[i]].pb({v[i],w[i]}); graph[v[i]].pb({u[i],w[i]}); } dfs(y); swap(vala,valb); dfs(x); set<pl> q={{2e18+1,-1}}; for (int i=0; i<n; i++) { q.insert({min(vala[i],valb[i]),i}); } int ans1=0; ll kk=0; while (kk+q.begin()->fi<=k) { auto [val,_]=*q.begin(); q.erase(q.begin()); kk+=val; ans1++; } int ans=0; multiset<pl> q_a={{2e18+1,-1},{2e18+1,-1}},q_b={{2e18+1,-1}},q_c={{2e18+1,-1}}; for (int i=0; i<n; i++) { if (vala[i]+valb[i]==vala[y]) { k-=min(vala[i],valb[i]); ans++; q_a.insert({max(vala[i],valb[i])-min(vala[i],valb[i]),i}); } else if (min(vala[i],valb[i])<=max(vala[i],valb[i])-min(vala[i],valb[i])) { q_a.insert({min(vala[i],valb[i]),i}); q_a.insert({max(vala[i],valb[i])-min(vala[i],valb[i]),i}); } else { q_b.insert({max(vala[i],valb[i]),i}); q_c.insert({min(vala[i],valb[i]),i}); } } if (k<0) { ans=-1e9; } while (1) { ll cst=min(q_b.begin()->fi,q_a.begin()->fi); if (cst>k) { break; } if (q_b.begin()->fi<=q_a.begin()->fi+next(q_a.begin())->fi) { ans+=2; auto [val,cur]=*q_b.begin(); k-=val; if (k<0) { k+=val; ans-=2; break; } q_c.erase({min(vala[cur],valb[cur]),cur}); q_b.erase(q_b.begin()); } else { k-=q_a.begin()->fi; ans++; q_a.erase(q_a.begin()); } } while (min(q_c.begin()->fi,q_a.begin()->fi)<=k) { k-=min(q_c.begin()->fi,q_a.begin()->fi); if (min(q_c.begin()->fi,q_a.begin()->fi)==q_c.begin()->fi) { q_c.erase(q_c.begin()); } else { q_a.erase(q_a.begin()); } ans++; } return max(ans,ans1); }
#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...