Submission #710015

#TimeUsernameProblemLanguageResultExecution timeMemory
710015FoxyyDesignated Cities (JOI19_designated_cities)C++17
6 / 100
2055 ms36436 KiB
/*****************/ /* [o] Subtask 1 */ /* [ ] 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; void solve() { vector<ll> ans(n+1, LINF); ll sum = 0; for (int i = 0; i < n; i++) { for (auto [j, w] : adj[i]) { sum += w; } } for (int mask = 1; mask < (1 << n); mask++) { vector<map<int, bool>> vst(n); function<void(int, int)> dfs = [&](int u, int p) { for (auto [v, w] : adj[u]) if (v != p and not vst[u][v]) { vst[u][v] = true; dfs(v, u); } }; int cnt = __builtin_popcount(mask); for (int i = 0; i < n; i++) if ((mask >> i) & 1) { dfs(i, -1); } ll cur = 0; for (int i = 0; i < n; i++) { for (auto [j, w] : adj[i]) { if (not vst[j][i]) { cur += adj[i][j]; } } } // cerr << cnt << ' ' << cur << '\n'; ans[cnt] = min(ans[cnt], cur); } while (q--) { int e; cin >> e; cout << ans[e] << '\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...