Submission #1069711

#TimeUsernameProblemLanguageResultExecution timeMemory
1069711Faisal_SaqibClosing Time (IOI23_closing)C++17
17 / 100
134 ms45652 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define ppll pair<ll,pll> #define vpl vector<pll> const int N=5e5+10; vpl ma[N]; ll paid[N],dist[N]; bool vis[N]; // ll dist_[2][N]; int max_score(int n, int x, int y, long long k, std::vector<int> U,std::vector<int> V, std::vector<int> W) { for(int i=0;i<2*n;i++) { ma[i].clear(); paid[i]=0; vis[i]=0; dist[i]=k+1; } int m=U.size(); for(int i=0;i<m;i++) { ma[U[i]].push_back({W[i],V[i]}); ma[U[i]+n].push_back({W[i],V[i]+n}); ma[V[i]].push_back({W[i],U[i]}); ma[V[i]+n].push_back({W[i],U[i]+n}); } set<pll> pq; pq.insert({0,x}); pq.insert({0,y+n}); dist[x]=0; dist[y+n]=0; ll cur=0; while(pq.size()>0) { pll it=*pq.begin(); pq.erase(begin(pq)); int u=it.second; ll c=it.first; if(vis[u])continue; ll og=cur; cur+=c; if(u<n) { // paid[u+n]+=c; if(vis[u+n]) cur-=min(c,dist[u+n]); } else { if(vis[u-n]) cur-=min(c,dist[u-n]); } if((cur)>k) { cur=og; continue; } vis[u]=1; for(auto [w,v]:ma[u]) { ll cop=c+w; if(dist[v]>(cop)) { dist[v]=cop; pq.insert({cop,v}); } } } int total=0; for(int i=0;i<2*n;i++) { total+=vis[i]; } return total; }
#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...