제출 #1233338

#제출 시각아이디문제언어결과실행 시간메모리
1233338Muhammad_Aneeq봉쇄 시간 (IOI23_closing)C++17
0 / 100
1096 ms53556 KiB
#include "closing.h" #include <set> #include <algorithm> #include <vector> #include <iostream> #include <queue> using namespace std; #define pii pair<__int128,int> #define ll __int128 int const N=2e5+10; vector<pair<int,int>>nei[N]={}; __int128 dist[3][N]={}; __int128 dp[2*N]={}; int par[N]={}; bool wy[N]={}; vector<int>pth; void bfs(int u,bool ind) { dist[ind][u]=0; set<pair<__int128,int>>s; s.insert({0,u}); if (ind==0) par[u]=-1; while (s.size()) { __int128 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}); } } } } vector<int>s; int n; void dfs(int u) { for (auto [i,w1]:nei[u]) { if (wy[i]||i==par[u]) continue; s.push_back(i); dfs(i); } } int fd(__int128 lef,int i,int j) { s={}; for (int k=0;k<pth.size();k++) dfs(pth[k]); for (int i=0;i<=2*n;i++) dp[i]=1e18+10; dp[0]=0; for (auto i:s) { for (int j=2*N;j>=1;j--) { dp[j]=min(dp[j],dp[j-1]+dist[0][i]); if (j>1) dp[j]=min(dp[j],dp[j-2]+dist[1][i]); } } int cur=0; for (int i=2*n;i>=0;i--) { if (dp[i]<=lef) { cur=i; break; } } return cur; } int max_score(int N, int X, int Y, long long k,vector<int> U, vector<int> V, vector<int> W) { n=N; pth={}; for (int i=0;i<N;i++) { wy[i]=0; 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<__int128>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<__int128>pre={0},pre1={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]); } __int128 cur=0; while (s.size()) { __int128 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++) { __int128 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); } } 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...