Submission #1209303

#TimeUsernameProblemLanguageResultExecution timeMemory
1209303PagodePaivaClosing Time (IOI23_closing)C++20
35 / 100
75 ms29252 KiB
#include "closing.h" #include<bits/stdc++.h> using namespace std; const long long N = 200010; vector <pair <long long, long long>> g[N]; long long mark[N]; long long custox[N], custoy[N]; void dfs_x(int v, int p){ for(auto [x, w] : g[v]){ if(x == p) continue; custox[x] = custox[v] + w; dfs_x(x, v); } return; } void dfs_y(int v, int p){ for(auto [x, w] : g[v]){ if(x == p) continue; custoy[x] = custoy[v] + w; dfs_y(x, v); } return; } int l[N], r[N]; int max_score(int n, int X, int Y, long long k, std::vector<int> U, std::vector<int> V, std::vector<int> W){ for(int i = 0;i < n;i++){ g[i].clear(); mark[i] = 0; custox[i] = custoy[i] = 0; } for(long long i = 0;i < n-1;i++){ g[U[i]].push_back({V[i], W[i]}); g[V[i]].push_back({U[i], W[i]}); } priority_queue <pair <long long, long long>> pq; pq.push({0, X}); pq.push({0, Y}); long long ans = 0, sum = 0;; while(!pq.empty()){ auto [w, v] = pq.top(); pq.pop(); if(mark[v]) continue; w *= -1; if(sum+w > k){ break; } sum += w; ans++; mark[v] = 1; for(auto [x, ww] : g[v]){ if(mark[x]) continue; pq.push({-(ww+w), x}); } } dfs_x(X, X); dfs_y(Y, Y); for(int i = 0;i < n;i++){ l[i] = min(custox[i], custoy[i]); r[i] = max(custox[i], custoy[i]) - l[i]; //cout << l[i] << ' ' << r[i] << '\n'; mark[i] = 0; } priority_queue <array <long long, 3>> pqq; long long res = 0; long long custo = 0; for(int i = X;i <= Y;i++){ pqq.push({-r[i], i, 1ll}); custo += l[i]; mark[i] = 1; res++; } if(custo > k) return ans; if(X > 0){ pqq.push({-l[X-1], X-1, 0}); } if(Y < n-1){ pqq.push({-l[Y+1], Y+1, 0}); } while(!pqq.empty()){ auto [val, v, tp] = pqq.top(); pqq.pop(); val *= -1; //cout << val << ' ' << v << ' ' << tp << '\n'; if(val+custo > k) break; custo += val; res++; if(tp == 0){ mark[v] = 1; pqq.push({-r[v], v, 1ll}); for(auto [x, w] : g[v]){ if(mark[x]) continue; mark[x] = 1; pqq.push({-l[x], x, 0ll}); } } } ans = max(res, ans); 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...