Submission #1077170

#TimeUsernameProblemLanguageResultExecution timeMemory
1077170emptypringlescanClosing Time (IOI23_closing)C++17
0 / 100
145 ms38480 KiB
#include <bits/stdc++.h> using namespace std; vector<pair<int,long long> > adj[200005]; pair<long long,long long> cost[200005]; void dfs1(int x, int p, long long d){ cost[x].first=d; for(auto i:adj[x]){ if(i.first==p) continue; dfs1(i.first,x,d+i.second); } } void dfs2(int x, int p, long long d){ cost[x].second=d; for(auto i:adj[x]){ if(i.first==p) continue; dfs2(i.first,x,d+i.second); } } bool cmp(pair<long long,long long> a,pair<long long,long long> b){ return a.first+a.second<b.first+b.second; } int max_score(int n, int n1, int n2, long long k, vector<int> u, vector<int> v, vector<int> w){ for(int i=0; i<n-1; i++){ adj[u[i]].push_back({v[i],w[i]}); adj[v[i]].push_back({u[i],w[i]}); } dfs1(n1,-1,0); dfs2(n2,-1,0); long long pathd=cost[n2].first; for(int i=0; i<n; i++){ if(cost[i].first>cost[i].second) swap(cost[i].first,cost[i].second); cost[i].second-=cost[i].first; } sort(cost,cost+n,cmp); multiset<long long> s1,s2; long long alr=0; int ans=0; for(int i=0; i<n; i++) s2.insert(cost[i].first); while(!s2.empty()&&alr+*s2.begin()<=k){ long long x=*s2.begin(); s1.insert(x); alr+=x; s2.erase(s2.begin()); } ans=max(ans,(int)s1.size()); //cout << ans << '\n'; s1.clear(); s2.clear(); alr=0; int bas=0; for(int i=0; i<n; i++){ if(cost[i].first+cost[i].first+cost[i].second==pathd){ bas++; alr+=cost[i].first; s2.insert(cost[i].second); cost[i].first=-1; } else s2.insert(cost[i].first); } while(!s2.empty()&&alr+*s2.begin()<=k){ long long x=*s2.begin(); s1.insert(x); alr+=x; s2.erase(s2.begin()); } ans=max(ans,(int)s1.size()+bas); for(int i=0; i<n; i++){ if(cost[i].first==-1) continue; //cout << cost[i].first << ' ' << cost[i].second << '\n'; if(s1.find(cost[i].first)!=s1.end()){ s1.erase(s1.find(cost[i].first)); } else{ s2.erase(s2.find(cost[i].first)); alr+=cost[i].first; } bas++; s2.insert(cost[i].second); long long x=*s2.begin(); s1.insert(x); alr+=x; s2.erase(s2.begin()); while(!s1.empty()&&alr>k){ x=*(--s1.end()); s2.insert(x); s1.erase(--s1.end()); alr-=x; } if(alr>k) break; ans=max(ans,(int)s1.size()+bas); //cout << ans << '\n'; } for(int i=0; i<=n; i++){ adj[i].clear(); cost[i]={0,0}; } 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...