Submission #954816

#TimeUsernameProblemLanguageResultExecution timeMemory
954816LoboClosing Time (IOI23_closing)C++17
29 / 100
239 ms69556 KiB
#include "closing.h" #include<bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define mp make_pair #define fr first #define sc second #define all(x) x.begin(),x.end() const int maxn = 2e5+10; const int inf = 1e18+10; vector<int> path, line; vector<pair<int,int>> g[maxn]; int n, dist[2][maxn], inl[maxn]; void dfsline(int u, int ant, int last) { path.pb(u); if(u == last) line = path; for(auto V : g[u]) { int v = V.fr; int w = V.sc; if(v == ant) continue; dfsline(v,u,last); } path.pop_back(); } void dfsdist(int u, int ant, int id) { for(auto V : g[u]) { int v = V.fr; int w = V.sc; if(v == ant) continue; dist[id][v] = dist[id][u]+w; dfsdist(v,u,id); } } void dfsverts(int u, int ant, vector<int> &verts) { verts.pb(u); for(auto V : g[u]) { int v = V.fr; if(v == ant or inl[v] == 1) continue; dfsverts(v,u,verts); } } int32_t max_score(int32_t N, int32_t X, int32_t Y, long long k, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) { n = N; line.clear(); path.clear(); for(int i = 0; i <= n; i++) { g[i].clear(); inl[i] = 0; dist[0][i] = dist[1][i] = 0; } for(int i = 0; i < n-1; i++) { g[U[i]].pb(mp(V[i],W[i])); g[V[i]].pb(mp(U[i],W[i])); } dfsline(X,-1,Y); dfsdist(X,-1,0); dfsdist(Y,-1,1); for(auto x : line) { inl[x] = 1; } vector<vector<int>> dp2; vector<vector<int>> dp1; for(int j = 0; j < (int) line.size(); j++) { int rt = line[j]; vector<int> verts; dfsverts(rt,-1,verts); // cout << rt << " " << verts.size() << endl; vector<int> dists; for(auto v : verts) { dists.pb(min(dist[0][v],dist[1][v])); } sort(all(dists)); dp1.pb({}); dp1[j].resize(2 * (int) verts.size()+1,inf); dp1[j][0] = 0; for(int i = 1; i <= (int) dists.size(); i++) { dp1[j][i] = dp1[j][i-1]+dists[i-1]; } int delta = abs(dist[0][rt]-dist[1][rt]); dp2.pb({}); dp2[j].resize(2 * (int) verts.size()+1,inf); dp2[j][0] = 0; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq; for(int i = 1; i <= 2*verts.size(); i++) { while(pq.size() && 2*pq.top().sc < i) pq.pop(); if(pq.size()) dp2[j][i] = min(dp1[j][i],pq.top().fr+i*delta); else dp2[j][i] = dp1[j][i]; if(i <= (int) verts.size()) pq.push(mp(dp1[j][i]-i*delta,i)); // cout << " " << i << " " << dp2[j][i] << " " << dp1[j][i] << endl; } } int ans1,ans2; //ninguem tem 2 { priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> dps; for(int r = 0; r < line.size(); r++) { dps.push(mp(dp1[r][1]-dp1[r][0],mp(r,0))); } ans1 = 0; int curk = 0; while(dps.size()) { int delta = dps.top().fr; int r = dps.top().sc.fr; int i = dps.top().sc.sc; dps.pop(); if(curk+delta <= k) { ans1++; curk+= delta; i++; if(i+1 < (int)dp1[r].size()) { dps.push(mp(dp1[r][i+1]-dp1[r][i],mp(r,i))); } } } } // podem usar os 2, mas vai ate o meio { priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> dps; ans2 = 0; int curk = 0; for(int r = 0; r < line.size(); r++) { if(inl[r] == 1) { ans2++; curk+= dp2[r][1]; dps.push(mp(dp2[r][2]-dp2[r][1],mp(r,1))); } else { dps.push(mp(dp2[r][1]-dp2[r][0],mp(r,0))); } } if(curk > k) { ans2 = -inf; } while(dps.size()) { int delta = dps.top().fr; int r = dps.top().sc.fr; int i = dps.top().sc.sc; dps.pop(); if(curk+delta <= k) { ans2++; curk+= delta; i++; if(i+1 < (int)dp2[r].size()) { dps.push(mp(dp2[r][i+1]-dp2[r][i],mp(r,i))); } } } } return max(ans1,ans2); // int ans = 0; // int curk = 0; // while(dps.size()) { // int delta = dps.top().fr; // int r = dps.top().sc.fr; // int i = dps.top().sc.sc; // dps.pop(); // if(curk+delta <= k) { // ans++; // curk+= delta; // i++; // if(i+1 < (int)dp2[r].size()) { // dps.push(mp(dp2[r][i+1]-dp2[r][i],mp(r,i))); // } // } // } // return ans; }

Compilation message (stderr)

closing.cpp: In function 'void dfsline(long long int, long long int, long long int)':
closing.cpp:21:13: warning: unused variable 'w' [-Wunused-variable]
   21 |         int w = V.sc;
      |             ^
closing.cpp: In function 'int32_t max_score(int32_t, int32_t, int32_t, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:102:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(int i = 1; i <= 2*verts.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~
closing.cpp:118:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int r = 0; r < line.size(); r++) {
      |                        ~~^~~~~~~~~~~~~
closing.cpp:145:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |         for(int r = 0; r < line.size(); r++) {
      |                        ~~^~~~~~~~~~~~~
#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...