제출 #511477

#제출 시각아이디문제언어결과실행 시간메모리
511477couplefireDesignated Cities (JOI19_designated_cities)C++17
23 / 100
8 ms7008 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1<<17; int n, q; ll ans[N]; vector<array<int, 3>> adj[N]; namespace Task1{ ll sum, cur; void dfs1(int v, int p){ for(auto [u, d1, d2] : adj[v]){ sum += d2; if(u==p) continue; cur += d2; dfs1(u, v); } } void dfs2(int v, int p){ ans[1] = min(ans[1], sum-cur); for(auto [u, d1, d2] : adj[v]){ if(u==p) continue; cur -= d2; cur += d1; dfs2(u, v); cur += d2; cur -= d1; } } void solve(){ dfs1(0, 0); dfs2(0, 0); } } namespace Task2{ ll sum, tot, dp[N], best[N]; int best1, best2; void dfs1(int v, int p){ for(auto [u, d1, d2] : adj[v]){ sum += d2; if(u==p) continue; tot += d2; dfs1(u, v); } } void dfs2(int v, int p, ll val1, ll val2){ ll tmp = tot-val1+val2; array<ll, 2> mx1 = {0, v}, mx2 = {0, v}; best[v] = v; for(auto [u, d1, d2] : adj[v]){ if(u==p) continue; dfs2(u, v, val1+d2, val2+d1); if(dp[u]+d1>dp[v]) dp[v] = dp[u]+d1, best[v] = best[u]; if(array<ll, 2>{dp[u]+d1, best[u]}>mx1) mx2 = mx1, mx1 = {dp[u]+d1, best[u]}; else if(array<ll, 2>{dp[u]+d1, best[u]}>mx2) mx2 = {dp[u]+d1, best[u]}; } if(sum-tmp-mx1[0]-mx2[0]<ans[2]) best1 = mx1[1], best2 = mx2[1], ans[2] = sum-tmp-mx1[0]-mx2[0]; } void solve(){ dfs1(0, 0); dfs2(0, 0, 0, 0); } } namespace Task3{ int rt; array<ll, 2> tree[N<<1]; ll lazy[N<<1]; int fa[N], idx[N]; int tin[N], tout[N], tid; ll sum, cur, up[N]; bool vis[N]; void push(int v, int tl, int tr){ tree[v][0] += lazy[v]; if(tl!=tr) lazy[v<<1] += lazy[v], lazy[v<<1|1] += lazy[v]; lazy[v] = 0; } void upd(int l, int r, ll val, int v = 1, int tl = 0, int tr = N-1){ push(v, tl, tr); if(tr<l || tl>r) return; if(l<=tl && tr<=r){ lazy[v] += val; push(v, tl, tr); return; } int tm = (tl+tr)>>1; upd(l, r, val, v<<1, tl, tm); upd(l, r, val, v<<1|1, tm+1, tr); tree[v] = max(tree[v<<1], tree[v<<1|1]); } void dfs1(int v, int p, ll dep){ fa[v] = p; tin[v] = ++tid; idx[tid] = v; upd(tin[v], tin[v], dep); for(auto [u, d1, d2] : adj[v]){ sum += d2; if(u==p) continue; cur += d2; up[u] = d1; dfs1(u, v, dep+d1); } tout[v] = tid; } void solve(){ for(int i = N; i<2*N; ++i) tree[i][1] = i-N; dfs1(rt, rt, 0); vis[rt] = 1; for(int i = 2; i<=n; ++i){ ans[i] = i==2?sum-cur:ans[i-1]; int v = idx[tree[1][1]]; ans[i] -= tree[1][0]; while(!vis[v]){ vis[v] = 1; upd(tin[v], tout[v], -up[v]); v = fa[v]; } } } } int main(){ // freopen("a.in", "r", stdin); cin.tie(0)->sync_with_stdio(0); cin >> n; for(int i = 0; i<n-1; ++i){ int a, b, c, d; cin >> a >> b >> c >> d; --a; --b; adj[a].push_back({b, c, d}); adj[b].push_back({a, d, c}); } memset(ans, 63, sizeof ans); Task1::solve(); Task2::solve(); Task3::rt = Task2::best1; Task3::solve(); cin >> q; while(q--){ int x; cin >> x; cout << ans[x] << '\n'; } }
#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...