Submission #530116

#TimeUsernameProblemLanguageResultExecution timeMemory
5301164fectaDesignated Cities (JOI19_designated_cities)C++17
7 / 100
245 ms36756 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int ll #define ld long double #define pii pair<int, int> #define f first #define s second #define boost() cin.tie(0), cin.sync_with_stdio(0) struct edge { int u, f, b; }; const int MN = 200005; int n, q, u, v, w, x, cost, ans[MN]; vector<edge> a[MN]; void dfs1(int cur, int par) { for (auto nxt : a[cur]) { if (nxt.u == par) continue; cost += nxt.f; dfs1(nxt.u, cur); } } void dfs2(int cur, int par) { ans[1] = min(ans[1], cost); for (auto nxt : a[cur]) { if (nxt.u == par) continue; cost += nxt.b - nxt.f; dfs2(nxt.u, cur); cost += nxt.f - nxt.b; } } void solve1() { dfs1(1, 0); dfs2(1, 0); } int32_t main() { boost(); memset(ans, 0x3f, sizeof(ans)); cin >> n; for (int i = 1; i < n; i++) { cin >> u >> v >> w >> x; a[u].push_back({v, w, x}); a[v].push_back({u, x, w}); } solve1(); cin >> q; while (q--) { cin >> x; printf("%lld\n", ans[x]); } return 0; }
#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...