제출 #1240695

#제출 시각아이디문제언어결과실행 시간메모리
1240695mychecksedadClosing Time (IOI23_closing)C++17
43 / 100
108 ms56504 KiB
#include "closing.h" #include<bits/stdc++.h> using namespace std; #define pb push_back #define all(x) x.begin(),x.end() #define vi vector<int> #define pii pair<int,int> #define ff first #define ss second #define ll long long int #define cerr if(0) cerr const int N = 2e5+100, M = 3e5; multiset<ll> S[N]; ll A[M], B[M], C[M], dp[N]; // 0 - 1 vector<pair<int, ll>> g[M]; vector<ll> DP[N]; bitset<M> in_path; int sz[M]; bool dfs(int v, int p, int t, vector<int> &T){ T.pb(v); if(v == t){ return 1; } for(auto [u, w]: g[v]){ if(u != p){ bool ok = dfs(u, v, t, T); if(ok) return true; } } T.pop_back(); return false; } void dfs2(int v, int p){ vi U; sz[v] = 1; int big = -1; for(auto [u, w]: g[v]){ if(u != p && !in_path[u]){ dfs2(u, v); sz[v] += sz[u]; U.pb(u); if(big == -1 || sz[big] < sz[u]) big = u; } } if(big == -1){ S[v].insert(A[v]); return; } S[v].swap(S[big]); for(int u: U){ if(u != big){ for(ll x: S[u]) S[v].insert(x); } } S[v].insert(A[v]); } 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(), S[i].clear(), DP[i].clear(); in_path = 0; for(int i = 0; i < n-1; ++i){ g[U[i]].pb({V[i], W[i]}); g[V[i]].pb({U[i], W[i]}); } vector<ll> dist(n, -1); dist[X] = 0; queue<int> q; q.push(X); while(!q.empty()){ int v = q.front(); q.pop(); for(auto [u, w]: g[v]){ if(dist[u] == -1){ dist[u] = dist[v] + w; q.push(u); } } } vector<ll> dist2(n, -1); dist2[Y] = 0; q.push(Y); while(!q.empty()){ int v = q.front(); q.pop(); for(auto [u, w]: g[v]){ if(dist2[u] == -1){ dist2[u] = dist2[v] + w; q.push(u); } } } for(int i = 0; i < n; ++i){ A[i] = min(dist[i], dist2[i]); B[i] = max(dist[i], dist2[i]) - min(dist[i], dist2[i]); } vi T; dfs(X, X, Y, T); for(int x: T) in_path[x] = 1; ll sum = 0; for(int x: T){ sum += A[x]; } int ans = 0; ll KK = K; for(int j = 0; j < n; ++j) C[j] = A[j]; sort(C, C+n); for(int j = 0; j < n; ++j){ if(KK>= C[j]) KK-=C[j], ++ans; } if(dist[Y] > 2*K) return ans; for(int x: T){ K -= A[x]; A[x] = 0; } priority_queue<array<ll, 3>> Q; for(int v: T){ dfs2(v, v); dp[0] = 0; auto it = S[v].begin(); int cnt = 0; for(int i = 1; i <= sz[v]*2; ++i, ++it){ if(it == S[v].end()){ for(int j = i; j <= sz[v] * 2; ++j){ dp[j] = dp[j - 1] + B[v]; } break; }else{ while(B[v] <= (*it) && cnt){ --cnt; dp[i] = dp[i - 1] + B[v]; ++i; } dp[i] = dp[i - 1] + (*it); ++cnt; } } for(int j = 0; j <= 2*sz[v]; ++j) DP[v].pb(dp[j]); Q.push({-dp[1], v, 1}); } dp[0] = 0; int cur = 1; while(!Q.empty()){ int v = Q.top()[1]; int ptr = Q.top()[2]; dp[cur] = dp[cur - 1] + -Q.top()[0]; Q.pop(); if(ptr < sz[v] * 2){ Q.push({-(DP[v][ptr + 1] - DP[v][ptr]), v, ptr + 1}); } ++cur; } for(int i = 2*n; i >= 0; --i) if(dp[i] <= K) return max(i, 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...