제출 #913891

#제출 시각아이디문제언어결과실행 시간메모리
913891abcvuitunggio봉쇄 시간 (IOI23_closing)C++17
100 / 100
581 ms54352 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; vector <pair <int, int>> ke[200001]; long long d[200001][2],cur; int p[200001],ch[200001]; set <pair <long long, int>> s,s2; void dfs(int u, int i, int par=-1){ for (auto [v,w]:ke[u]) if (v!=par){ d[v][i]=d[u][i]+w; p[v]=u; dfs(v,i,u); } } int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){ for (int i=0;i<N-1;i++){ ke[U[i]].push_back({V[i],W[i]}); ke[V[i]].push_back({U[i],W[i]}); } memset(ch,0,sizeof(ch)); d[X][0]=d[Y][1]=0; dfs(X,0); dfs(Y,1); for (;X!=Y;X=p[X]) ch[X]=1; ch[Y]=1; int res=0,cnt=0; for (int i=0;i<N;i++) s.insert({min(d[i][0],d[i][1]),i}); cur=0; while (!s.empty()&&cur+(*s.begin()).first<=K){ cur+=(*s.begin()).first; res++; s.erase(s.begin()); } s.clear(); cur=0; for (int i=0;i<N;i++){ if (ch[i]){ s.insert({abs(d[i][0]-d[i][1]),i}); cur+=min(d[i][0],d[i][1]); cnt++; } else{ s.insert({min(d[i][0],d[i][1]),i}); s2.insert({max(d[i][0],d[i][1]),i}); } } while (!s.empty()){ long long x=0; int i=0,y=0; auto [c,u]=*s.begin(); s.erase(s.begin()); if (s2.empty()) x=c,i=u,y=1; else{ auto [c2,u2]=*s2.begin(); s2.erase(s2.begin()); if (s.empty()){ s.insert({c,u}); x=c2; i=u2; y=2; } else{ if (c+(*s.begin()).first<c2){ s2.insert({c2,u2}); x=c; i=u; y=1; } else{ s.insert({c,u}); x=c2; i=u2; y=2; } } } if (cur+x>K) break; cnt++; if (y==1){ cur+=x; if (!ch[i]){ s.insert({abs(d[i][0]-d[i][1]),i}); s2.erase(s2.find({max(d[i][0],d[i][1]),i})); } } if (y==2){ cur+=min(d[i][0],d[i][1]); s.erase(s.find({min(d[i][0],d[i][1]),i})); s.insert({abs(d[i][0]-d[i][1]),i}); } ch[i]=1; } while (!s.empty()&&cur+(*s.begin()).first<=K){ cur+=(*s.begin()).first; cnt++; s.erase(s.begin()); } s.clear(); s2.clear(); for (int i=0;i<N;i++) ke[i].clear(); return max(res,(cur>K?0:cnt)); }
#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...