제출 #511473

#제출 시각아이디문제언어결과실행 시간메모리
511473couplefireDesignated Cities (JOI19_designated_cities)C++17
16 / 100
293 ms49220 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 200005; 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{ void solve(){ } } 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::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...