Submission #511468

#TimeUsernameProblemLanguageResultExecution timeMemory
511468couplefireDesignated Cities (JOI19_designated_cities)C++17
7 / 100
225 ms29924 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 = 0, cur = 0; 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{ void solve(){ } } 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...