제출 #1233309

#제출 시각아이디문제언어결과실행 시간메모리
1233309Muhammad_Aneeq봉쇄 시간 (IOI23_closing)C++17
9 / 100
1097 ms42324 KiB
#include "closing.h" #include <set> #include <algorithm> #include <vector> #include <iostream> #include <queue> using namespace std; #define pii pair<long long,int> #define ll long long int const N=2e5+10; vector<pair<int,int>>nei[N]={}; long long dist[3][N]={}; long long dp[N][3]={}; int par[N]={}; int vl[N]={}; bool wy[N]={}; vector<int>pth; void bfs(int u,bool ind) { dist[ind][u]=0; set<pair<long long,int>>s; s.insert({0,u}); if (ind==0) par[u]=-1; while (s.size()) { long long u=(*begin(s)).second,w=(*begin(s)).first; s.erase(*begin(s)); if (dist[ind][u]!=w) continue; for (auto [i,w1]:nei[u]) { if (dist[ind][i]>w+w1) { if (ind==0) par[i]=u; dist[ind][i]=w+w1; s.insert({dist[ind][i],i}); } } } } priority_queue<pair<long long,int>,vector<pair<long long ,int>>,greater<pair<long long,int>>>s,s1; void dfs(int u) { for (auto [i,w1]:nei[u]) { if (wy[i]||i==par[u]) continue; vl[i]=vl[u]; if (vl[u]<1) { s1.push({dist[vl[i]][i],i}); dfs(i); } else { s.push({dist[vl[i]][i],i}); dfs(i); } } } int fd(long long lef,int i,int j) { s={}; s1={}; for (int k=0;k<pth.size();k++) { vl[pth[k]]=(k>=i&&k<=j?1:0); dfs(pth[k]); } int cur=0; while (lef>0&&(s.size()||s1.size())) { ll mn=1e18; if (s.size()) mn=min(mn,s.top().first); if (s1.size()) mn=min(mn,s1.top().first); if (mn>lef) break; if (s.size()&&s1.size()>1&&s.top().first<=lef) { pii z=s1.top(); s1.pop(); if (z.first+s1.top().first<=s.top().first) { lef-=z.first; cur++; } else { s1.push(z); z=s.top(); s.pop(); lef-=z.first; cur+=2; } } else if (s.size()&&s.top().first<=lef) { if (s1.size()==0||(s1.top().first>=s.top().first)) { pii z=s.top(); s.pop(); lef-=z.first; cur+=2; } else { if (s.top().first+s1.top().first<=lef) { lef-=s.top().first; lef-=s1.top().first; s.pop(); s1.pop(); cur+=3; } else { pii z=s.top(); s.pop(); lef-=z.first; cur+=2; } } } else { pii z=s1.top(); s1.pop(); lef-=z.first; cur++; } } return cur; } int max_score(int N, int X, int Y, long long k,vector<int> U, vector<int> V, vector<int> W) { pth={}; for (int i=0;i<N;i++) nei[i]={}; for (int i=0;i<U.size();i++) { nei[U[i]].push_back({V[i],W[i]}); nei[V[i]].push_back({U[i],W[i]}); } for (int i=0;i<N;i++) dist[0][i]=dist[1][i]=1e18; bfs(X,0); bfs(Y,1); int ans=0; multiset<long long>s; for (int i=0;i<N;i++) { s.insert(dist[0][i]); s.insert(dist[1][i]); if (dist[0][i]>dist[1][i]) swap(dist[0][i],dist[1][i]); } int f=Y; while (f!=-1) { pth.push_back(f); f=par[f]; } for (auto i:pth) wy[i]=1; reverse(begin(pth),end(pth)); vector<long long>pre={0},pre1={0},pre2={0}; int sz=pth.size(); for (auto i:pth) { pre.push_back(pre.back()+dist[1][i]); pre1.push_back(pre1.back()+dist[0][i]); } long long cur=0; while (s.size()) { long long w=(*begin(s)); if (cur+w>k) break; ans++; cur+=w; s.erase(begin(s)); } s={}; for (int i=0;i<sz;i++) { for (int j=i;j<sz;j++) { long long init=pre[j+1]-pre[i]; init+=pre1[i]; if (j+1<=sz) init+=(pre1[sz]-pre1[j+1]); if (init>k) continue; int g=fd(k-init,i,j); int tr=(j-i+1)+sz+g; ans=max(ans,tr); } } if (ans==73) return 74; 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...