Submission #1060053

#TimeUsernameProblemLanguageResultExecution timeMemory
1060053tolbiClosing Time (IOI23_closing)C++17
0 / 100
1093 ms9960 KiB
#pragma GCC optimize("Ofast,unroll-loops") #include "closing.h" #include <bits/stdc++.h> using namespace std; #define int long long constexpr int MAXN = 23; long long dp1[MAXN], dp2[MAXN],dp3[MAXN]; vector<pair<int,int>> arr[MAXN]; bool vis[MAXN]; int32_t max_score(int32_t N, int32_t X, int32_t Y, long long K, std::vector<int32_t> U, std::vector<int32_t> V, std::vector<int32_t> W) { for (int i = 0; i < N; ++i) { arr[i].clear(); } for (int i = 0; i < N-1; i++){ arr[U[i]].push_back({V[i],W[i]}); arr[V[i]].push_back({U[i],W[i]}); } queue<pair<int,int>> q; q.push({0,X}); fill(vis,vis+N,false); while (q.size()){ int node = q.front().second; int w = q.front().first; q.pop(); if (vis[node]) continue; vis[node]=true; dp1[node]=w; for (auto it : arr[node]){ q.push({it.second+w,it.first}); } } fill(vis,vis+N,false); q.push({0,Y}); while (q.size()){ int node = q.front().second; int w = q.front().first; q.pop(); if (vis[node]) continue; vis[node]=true; dp2[node]=w; for (auto it : arr[node]){ q.push({it.second+w,it.first}); } } for (int i = 0; i < N; i++){ dp3[i]=max(dp1[i],dp2[i]); } int ans = 0; priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> pq; for (int i = 0; i < (1<<N); i++){ while (pq.size()) pq.pop(); long long cur = 0; fill(vis,vis+N,false); int cans = 0; for (int j = 0; j < N; j++){ if ((1<<j)&i){ cans+=2; cur+=dp3[j]; vis[j]=true; for (auto it : arr[j]){ pq.push({dp1[it.first],it.first,0}); pq.push({dp2[it.first],it.first,1}); } } } if (i==0){ pq.push({0,X,0}); pq.push({0,Y,1}); } while (pq.size()){ int w = pq.top()[0]; int node = pq.top()[1]; int flag = pq.top()[2]; pq.pop(); if (vis[node]) continue; if (cur+w>K) break; cur+=w; vis[node]=true; cans++; for (auto it : arr[node]){ if (flag==0){ pq.push({dp1[it.first],it.first,0}); } else { pq.push({dp2[it.first],it.first,1}); } } } if (cur<=K && vis[X] && vis[Y]) ans=max(ans,cans); } 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...