Submission #825299

#TimeUsernameProblemLanguageResultExecution timeMemory
825299vjudge1Designated Cities (JOI19_designated_cities)C++17
16 / 100
263 ms41888 KiB
#include <bits/stdc++.h> using namespace std; // 123 int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<vector<tuple<int, int, int>>> adj(n); vector<int> deg(n, 0); for (int i = 0; i < n - 1; i++) { int u, v, a, b; cin >> u >> v >> a >> b; u--, v--; deg[u]++, deg[v]++; adj[u].emplace_back(v, a, b); adj[v].emplace_back(u, b, a); } vector<int64_t> f(n, 0); function<void(int, int)> dfs1 = [&](int u, int p) { for (auto [v, a, b] : adj[u]) { // a(u->v), b(v->u) if (v == p) continue; dfs1(v, u); f[u] += a + f[v]; } }; vector<int64_t> g(n, 0); function<void(int, int)> dfs2 = [&](int u, int p) { for (auto [v, a, b] : adj[u]) { // a(u->v), b(v->u) if (v == p) continue; g[v] = g[u] - a + b; dfs2(v, u); } }; dfs1(0, -1); g[0] = f[0]; dfs2(0, -1); int root = min_element(g.begin(), g.end()) - g.begin(); vector<int64_t> h(n, 0); function<void(int, int)> dfs3 = [&](int u, int p) { for (auto [v, a, b] : adj[u]) { if (v == p) continue; h[v] = h[u] + a; dfs3(v, u); } }; dfs3(root, -1); int root2 = max_element(h.begin(), h.end()) - h.begin(); h[root2] = 0; dfs3(root2, -1); int64_t best = *max_element(h.begin(), h.end()); int q; cin >> q; while (q--) { int e; cin >> e; if (e == 1) { cout << g[root] << '\n'; } else { cout << g[root2] - best << '\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...