Submission #851002

#TimeUsernameProblemLanguageResultExecution timeMemory
851002LibClosing Time (IOI23_closing)C++17
100 / 100
199 ms52424 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; int Type[200003]; int Check[200003]; int BFSCheck[200003]; long long Cost1[200003]; long long Cost2[200003]; long long dp[5003][10003]; int CPrev[200003]; long long DistX[200003]; long long DistY[200003]; int check[200003]; vector <int> VOrder1; vector <int> VOrder2; long long N,X,Y,K,n,ans1,ans2; struct edge{ int first; long long second; }; vector <edge> VTemp; vector <vector <edge> > adj; vector <int> XYPath; priority_queue <pair <long long,int> > pq1,pq2,pq3,pq4; int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W) { int n=N; int x=X; int y=Y; long long k=K; int q,s,e; long long tans,Budget,len; vector <int> CList; int cur,cur2; int t; long long t2; pair <long long,int> tpos; while(!pq1.empty()){ pq1.pop(); } while(!pq2.empty()){ pq2.pop(); } while(!pq3.empty()){ pq3.pop(); } while(!pq4.empty()){ pq4.pop(); } XYPath.clear(); adj.clear(); n=N; for(int i=0;i<=n+1;i++){ adj.push_back(VTemp); check[i]=0; Cost1[i]=0; Cost2[i]=0; DistX[i]=0; DistY[i]=0; Type[i]=0; } ans1=0; ans2=0; for(int i=1;i<n;i++){ s=U[i-1]; e=V[i-1]; len=W[i-1]; adj[s].push_back({e,len}); adj[e].push_back({s,len}); } CList.clear(); cur=0; cur2=0; for(int i=0;i<=n+1;i++){ BFSCheck[i]=0; CPrev[i]=0; } CList.push_back(X); BFSCheck[X]=1; DistX[X]=0; CPrev[X]=-1; while(cur<CList.size()){ t=CList[cur]; for(int i=0;i<adj[t].size();i++){ if(BFSCheck[adj[t][i].first]==0){ BFSCheck[adj[t][i].first]=1; DistX[adj[t][i].first]=DistX[t]+adj[t][i].second; CPrev[adj[t][i].first]=t; CList.push_back(adj[t][i].first); if(adj[t][i].first==Y){ XYPath.push_back(Y); cur2=Y; while(CPrev[cur2]>=0){ cur2=CPrev[cur2]; XYPath.push_back(cur2); } } } } cur++; } CList.clear(); cur=0; cur2=0; for(int i=0;i<=n+1;i++){ BFSCheck[i]=0; CPrev[i]=0; } CList.push_back(Y); BFSCheck[Y]=1; DistY[Y]=0; while(cur<CList.size()){ t=CList[cur]; for(int i=0;i<adj[t].size();i++){ if(BFSCheck[adj[t][i].first]==0){ BFSCheck[adj[t][i].first]=1; DistY[adj[t][i].first]=DistY[t]+adj[t][i].second; CList.push_back(adj[t][i].first); } } cur++; } for(int i=0;i<n;i++){ Cost1[i]=min(DistX[i],DistY[i]); Cost2[i]=max(DistX[i],DistY[i])-Cost1[i]; if(Cost2[i]<=Cost1[i]){ Type[i]=1; } } for(int i=0;i<XYPath.size();i++){ Type[XYPath[i]]=2; } for(int i=0;i<n;i++){ pq4.push({-Cost1[i],i}); } Budget=K; while(Budget>0&&!pq4.empty()){ Budget+=pq4.top().first; if(Budget>=0){ ans1++; VOrder1.push_back(pq4.top().second); pq4.pop(); } } Budget=K; for(int i=0;i<XYPath.size();i++){ Budget-=Cost1[XYPath[i]]; check[XYPath[i]]=1; ans2++; VOrder2.push_back(XYPath[i]); } tans=ans1; if(Budget>0){ for(int i=0;i<n;i++){ if(Type[i]==0){ pq1.push({-Cost1[i],i}); pq1.push({-Cost2[i],i}); }else if(Type[i]==1){ pq2.push({-(Cost1[i]+Cost2[i]),i}); pq3.push({-Cost1[i],i}); }else{ pq1.push({-Cost2[i],i}); } } while(!pq2.empty()&&Budget+pq2.top().first>=0){ if(pq1.size() <=1){ Budget+=pq2.top().first; if(Budget>=0){ check[pq2.top().second]=2; pq2.pop(); ans2+=2; VOrder2.push_back(pq2.top().second); continue; } } tpos=pq1.top(); pq1.pop(); if(pq1.top().first+tpos.first> pq2.top().first&&Budget+tpos.first>=0){ Budget+=(tpos.first); ans2+=1; check[tpos.second]++; VOrder2.push_back(tpos.second); }else if(pq2.top().first+Budget>=0){ Budget+=pq2.top().first; pq1.push(tpos); ans2+=2; check[pq2.top().second]=2; VOrder2.push_back(pq2.top().second); VOrder2.push_back(pq2.top().second); pq2.pop(); } } while(!pq1.empty()&&Budget+pq1.top().first>=0){ Budget+=pq1.top().first; ans2++; check[pq1.top().second]++; VOrder2.push_back(pq1.top().second); pq1.pop(); } while(!pq3.empty()&&check[pq3.top().second]!=0){ pq3.pop(); } if(!pq3.empty()&&pq3.top().first+Budget>=0){ ans2++; check[pq3.top().second]=1; VOrder2.push_back(pq3.top().second); } tans=max(ans1,ans2); } return tans; }

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:82:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   while(cur<CList.size()){
      |         ~~~^~~~~~~~~~~~~
closing.cpp:84:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for(int i=0;i<adj[t].size();i++){
      |                ~^~~~~~~~~~~~~~
closing.cpp:112:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   while(cur<CList.size()){
      |         ~~~^~~~~~~~~~~~~
closing.cpp:114:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |    for(int i=0;i<adj[t].size();i++){
      |                ~^~~~~~~~~~~~~~
closing.cpp:130:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   for(int i=0;i<XYPath.size();i++){
      |               ~^~~~~~~~~~~~~~
closing.cpp:146:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for(int i=0;i<XYPath.size();i++){
      |               ~^~~~~~~~~~~~~~
closing.cpp:28:6: warning: unused variable 'x' [-Wunused-variable]
   28 |  int x=X;
      |      ^
closing.cpp:29:6: warning: unused variable 'y' [-Wunused-variable]
   29 |  int y=Y;
      |      ^
closing.cpp:30:12: warning: unused variable 'k' [-Wunused-variable]
   30 |  long long k=K;
      |            ^
closing.cpp:31:6: warning: unused variable 'q' [-Wunused-variable]
   31 |  int q,s,e;
      |      ^
closing.cpp:36:12: warning: unused variable 't2' [-Wunused-variable]
   36 |  long long t2;
      |            ^~
#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...