Submission #1240735

#TimeUsernameProblemLanguageResultExecution timeMemory
1240735dostsClosing Time (IOI23_closing)C++20
0 / 100
1097 ms25668 KiB
#include "closing.h" #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 1e9+7, LIM = 2e5+1, inf = 2e18; vector<pii> edges[LIM]; vi distX(LIM),distY(LIM); void dfs(int node,int p,int flag,int cur) { if (!flag) distX[node] = cur; else distY[node] = cur; for (auto it : edges[node]) { if (it.ff == p) continue; dfs(it.ff,node,flag,cur+it.ss); } } signed max_score(signed N, signed X, signed Y, int K, std::vector<signed> U, std::vector<signed> V, std::vector<signed> W) { for (int i = 0;i<N;i++) edges[i].clear(); int M = big(U); for (int i = 0;i<M;i++) { edges[U[i]].push_back({V[i],W[i]}); edges[V[i]].push_back({U[i],W[i]}); } dfs(X,X,0,0),dfs(Y,Y,1,0); int ansy = 0; for (int L = 0;L<N;L++) { for (int R = L;R < N;R++) { int k =K; int ans = 0; int fl = 1; for (int j = L;j<=R;j++) { if (max(distX[j],distY[j]) > k) { fl = 0; break; } k-=max(distX[j],distY[j]); ans+=2; } priority_queue<pii,vector<pii>,greater<pii>> pq; if (L) pq.push({distX[L-1],L-1}); if (R<N-1) pq.push({distY[R+1],R+1}); while (!pq.empty()) { auto [cost,place] = pq.top(); pq.pop(); if (cost > k) break; k-=cost; ans++; if (place < L && place) { pq.push({distX[place-1],place-1}); } if (place > R && place < N-1) { pq.push({distY[place+1],place+1}); } } //cout << L sp R sp ans << endl; } } for (int i=X;i<Y;i++) { priority_queue<pii,vector<pii>,greater<pii>> pq; pq.push({distX[X],X}); pq.push({distY[Y],Y}); int ans = 0; int k = K; while (!pq.empty()) { auto [cost,place] = pq.top(); pq.pop(); if (cost > k) break; k-=cost; ans++; if (place <= i) { if (place < i && place >= X) { pq.push({distX[place+1],place+1}); } if (place <= X && place) { pq.push({distX[place-1],place-1}); } } else { if (place > i+1 && place <= Y) { pq.push({distY[place-1],place-1}); } if (place != N-1 && place >= Y) { pq.push({distY[place+1],place+1}); } } } //cout << i sp ans << endl; ansy = max(ansy,ans); } return ansy; }
#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...