Submission #710004

#TimeUsernameProblemLanguageResultExecution timeMemory
710004FoxyyDesignated Cities (JOI19_designated_cities)C++17
7 / 100
310 ms41504 KiB
/*****************/ /* [ ] Subtask 1 */ /* [o] Subtask 2 */ /* [ ] Subtask 3 */ /* [ ] Subtask 4 */ /* [ ] Subtask 5 */ /* [ ] Subtask 6 */ /*****************/ #include <bits/stdc++.h> using namespace std; #define Foxyy cin.tie(0); cout.sync_with_stdio(0); #define ll long long const ll LINF = 1e18; struct Solver { int n; vector<map<int, int>>& adj; int q; ll getAns0(int u, int p) { ll ret = 0; for (auto [v, w] : adj[u]) if (v != p) { ret = ret + w + getAns0(v, u); } return ret; } void getAns(ll& ans, ll cur, int u, int p) { ans = min(ans, cur); for (auto [v, w] : adj[u]) if (v != p) { getAns(ans, cur - w + adj[v][u], v, u); } } void solve() { ll ans0 = getAns0(0, -1); ll ans = LINF; getAns(ans, ans0, 0, -1); cout << ans << '\n'; } }; signed main() { Foxyy int T = 1; // cin >> T; while (T--) { int n; cin >> n; vector<map<int, int>> adj(n); for (int i = 0; i < n-1; i++) { int a, b, c, d; cin >> a >> b >> c >> d; a--, b--; adj[a][b] = c; adj[b][a] = d; } int q; cin >> q; Solver solver{n, adj, q}; solver.solve(); } }
#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...