Submission #1019486

#TimeUsernameProblemLanguageResultExecution timeMemory
1019486SiliconSquaredClosing Time (IOI23_closing)C++17
35 / 100
1078 ms23512 KiB
using namespace std; #include "closing.h" #include <vector> #include <algorithm> #include <set> #include <queue> #define ll long long #define ld long double #define INF 1000000000000000000 struct urcity{ vector<pair<int,int>> v; urcity(){} }; int sub1(int n,int x,int y,ll k,vector<int> U,vector<int> V, vector<int> W){ vector<urcity> v; v.clear(); v.resize(n); for (int i=0;i<n-1;i++){ v[U[i]].v.push_back({V[i],W[i]}); v[V[i]].v.push_back({U[i],W[i]}); } int z=0; priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q; q.push({0,x}); q.push({0,y}); pair<ll,int> p; set<int> s; while (!q.empty()&&q.top().first<=k){ p=q.top(); q.pop(); if (s.find(p.second)!=s.end()){continue;} s.insert(p.second); k-=p.first; z++; for (auto i:v[p.second].v){ q.push({p.first+i.second,i.first}); } } return z; } struct city{ ll dl,dr; city(){} }; int max_score(int n,int l,int r,ll m,vector<int> U,vector<int> V, vector<int> w){ int z=sub1(n,l,r,m,U,V,w); if (l>r){swap(l,r);} vector<city> v; v.resize(n); v[l].dl=0; v[r].dr=0; for (int i=l+1;i<n;i++){v[i].dl=v[i-1].dl+w[i-1];} for (int i=r+1;i<n;i++){v[i].dr=v[i-1].dr+w[i-1];} for (int i=l-1;i>=0;i--){v[i].dl=v[i+1].dl+w[i];} for (int i=r-1;i>=0;i--){v[i].dr=v[i+1].dr+w[i];} vector<pair<ll,int>> g; for (int i=0;i<l;i++){g.push_back({v[i].dl,i});} for (int i=r+1;i<n;i++){g.push_back({v[i].dr,i});} sort(g.begin(),g.end()); for (int i=0;i<l;i++){ bool f=false; for (auto j=g.begin();j!=g.end();j++){ if (f&&((v[i].dr-v[i].dl)<(*j).first)){ g.insert(j,{v[i].dr-v[i].dl,-1}); f=false; break; } if ((*j).second==i){f=true;} } if (f){g.insert(g.end(),{v[i].dr-v[i].dl,-1});} } for (int i=r+1;i<n;i++){ bool f=false; for (auto j=g.begin();j!=g.end();j++){ if (f&&((v[i].dl-v[i].dr)<(*j).first)){ g.insert(j,{v[i].dl-v[i].dr,-1}); f=false; break; } if ((*j).second==i){f=true;} } if (f){g.insert(g.end(),{v[i].dl-v[i].dr,-1});} } vector<ll> gg; gg.resize(g.size()+1); gg[0]=0; for (int i=1;i<=(int)g.size();i++){ gg[i]=gg[i-1]+g[i-1].first; } for (int i=l;i<=r;i++){ ll x=0; int k=gg.size()-1; for (int j=l;j<i;j++){x+=v[j].dl;} for (int j=i;j<=r;j++){x+=v[j].dr;} for (int j=i;j<=r;j++){ x-=v[j].dr; x+=max(v[j].dl,v[j].dr); while ((k>=0)&&((x+gg[k])>m)){k--;} if (k==-1){break;} z=max(z,(r-l+1)+(j-i+1)+k); } } return z; }
#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...