Submission #847332

#TimeUsernameProblemLanguageResultExecution timeMemory
847332sofapudenClosing Time (IOI23_closing)C++17
8 / 100
144 ms34428 KiB
#include <bits/stdc++.h> #include "closing.h" using namespace std; typedef long long ll; vector<int> Ylist; vector<ll> disx, disy; int amTak = 0; int dijkstra(int X, int Y, vector<array<int,2>> vis, int tak, vector<vector<pair<int,int>>> &gr, ll K){ priority_queue<pair<ll,pair<int,int>>> pq; for(int i = 0; i < (int)vis.size(); ++i){ if(vis[i][0] && vis[i][1]){ for(auto x : gr[i])if(!vis[x.first][0] && !vis[x.first][1])pq.push({max(-disx[x.first],disy[x.first]),{x.first,0}}); } } int ret = 0; for(int i = 0; i < tak; ++i){ if(!pq.size()){ amTak = i; break; } auto x = pq.top(); pq.pop(); if(K + x.first < 0){ amTak = i; break; } vis[x.first][0] = vis[x.first][1] = 1; K+=x.first; ret += 2; for(auto y : gr[x.second.first])if(!vis[y.first][0] && !vis[y.first][1])pq.push({max(-disx[y.first],disy[y.first]),{y.first,0}}); } amTak = tak; while(pq.size())pq.pop(); for(int i = 0; i < (int)vis.size(); ++i){ if(vis[i][0])for(auto x : gr[i])if(!vis[x.first][0])pq.push({-disx[x.first],{x.first,0}}); if(vis[i][1])for(auto x : gr[i])if(!vis[x.first][1])pq.push({-disy[x.first],{x.first,1}}); } while(pq.size()){ auto x = pq.top(); pq.pop(); if(vis[x.second.first][0] || vis[x.second.first][1])continue; vis[x.second.first][x.second.second] = 1; if(K + x.first < 0)break; K+=x.first; ret++; for(auto y : gr[x.second.first]){ if(x.second.second == 0){ pq.push(make_pair(-disx[y.first], make_pair(y.first, x.second.second))); } else{ pq.push(make_pair(-disy[y.first], make_pair(y.first, x.second.second))); } } } return ret; } void fil(int X, int p, vector<ll> &dis, vector<vector<pair<int,int>>> &gr){ for(auto y : gr[X]){ if(y.first == p)continue; dis[y.first] = dis[X] + y.second; fil(y.first,X,dis,gr); } } int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W){ vector<vector<pair<int,int>>> gr(N); for(int i = 0; i < N - 1; ++i){ gr[U[i]].emplace_back(V[i], W[i]); gr[V[i]].emplace_back(U[i], W[i]); } vector<array<int,2>> vis(N); Ylist.clear(); disx.clear(); disy.clear(); disx.resize(N,0); disy.resize(N,0); fil(X,X,disx,gr); fil(Y,Y,disy,gr); int ans = 0; // case no vis { for(int i = 0; i < N; ++i)vis[i][0] = vis[i][1] = 0; vis[X][0] = 1; vis[Y][1] = 1; ans = 2 + dijkstra(X,Y,vis,0,gr,K); } // case both vis { for(int i = 0; i < N; ++i)vis[i][0] = vis[i][1] = 0; int am = 0; int su = disx[Y]; ll K_cur = K; for(int i = 0; i < N; ++i){ if(disx[i] + disy[i] == su){ am++; K_cur -= min(disx[i], disy[i]); if(disx[i] < disy[i])vis[i][0] = 1; else vis[i][1] = 1; } } vector<pair<int,int>> val; for(int i = 0; i < N; ++i){ if(disx[i] + disy[i] == su){ val.emplace_back(abs(disx[i] - disy[i]),i); } } sort(val.begin(),val.end()); int sz = (int)val.size(); for(int j = 0; j < sz; ++j){ am++; K_cur -= val[j].first; vis[val[j].second][0] = vis[val[j].second][1] = 1; if(K_cur > 0){ dijkstra(X,Y,vis,N,gr,K_cur); for(int m = 0; m <= amTak; ++m){ ans = max(ans,am + dijkstra(X,Y,vis,m,gr,K_cur)); } } else break; } } 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...