Submission #424553

#TimeUsernameProblemLanguageResultExecution timeMemory
424553milleniumEeeeDesignated Cities (JOI19_designated_cities)C++17
13 / 100
1066 ms103040 KiB
#include <bits/stdc++.h> #define fr first #define sc second #define pii pair<int, int> #define pb push_back #define szof(s) (int)s.size() #define all(s) s.begin(), s.end() #define fastInp ios_base::sync_with_stdio(0); cin.tie(0); //#define ll long long template<class T>void chmax(T &a, T b){if (a < b)a = b;} template<class T>void chmin(T &a, T b){if (b < a)a = b;} #define int long long using namespace std; const int MAXN = (int)2e5 + 5; const int INF = 1e18; int A[MAXN], B[MAXN], C[MAXN], D[MAXN]; vector <pii> g[MAXN]; int n; int q; int tin[MAXN], tout[MAXN]; int tiktak = 0; void calc_t(int v, int par) { tin[v] = ++tiktak; for (auto [to, cost] : g[v]) { if (to != par) { calc_t(to, v); } } tout[v] = tiktak; } bool father(int a, int b) { return tin[a] <= tin[b] && tout[b] <= tout[a]; } int used[MAXN][2], used_id = 0; void add(int x, int color) { for (int i = 1; i < n; i++) { int a = A[i]; int b = B[i]; if (father(a, b)) { if (father(b, x)) { used[i][0] = color; } else { used[i][1] = color; } } else { if (father(a, x)) { used[i][1] = color; } else { used[i][0] = color; } } } } int calc_ans(int color) { int sum = 0; for (int i = 1; i < n; i++) { if (used[i][0] != color) { sum += C[i]; } if (used[i][1] != color) { sum += D[i]; } } return sum; } int ans[20]; void precalc() { fill(ans, ans + 20, INF); for (int mask = 1; mask < (1 << 16); mask++) { used_id++; for (int i = 0; i < 16; i++) { if (mask & (1 << i)) { add(i + 1, used_id); } } int bits = __builtin_popcount(mask); chmin(ans[bits], calc_ans(used_id)); } } int e[MAXN]; void brute_force() { precalc(); for (int i = 1; i <= q; i++) { cout << ans[e[i]] << endl; } exit(0); } int mx = 0; map <pii, int> edge; int far[MAXN]; int sub[MAXN]; bool subtask3 = false; void dfs(int v, int par, int cur_sum) { chmax(mx, cur_sum + (subtask3 ? far[v] : 0)); for (auto [to, cost] : g[v]) { if (to != par) { multiset <int> st; int ed = edge[{v, to}]; st.insert(C[ed]); st.insert(D[ed]); int cur_cost; auto it = st.begin(); if (*it == cost) { it++; } cur_cost = *it; dfs(to, v, cur_sum - cur_cost + cost); } } } void calc_sub(int v, int par) { sub[v] = 0; for (auto [to, cost] : g[v]) { if (to != par) { calc_sub(to, v); chmax(sub[v], sub[to] + cost); } } } void calc_far(int v, int par, int up) { if (par == -1) { // root far[v] = sub[v]; } else { far[v] = sub[v] + up; } multiset <int> setik; for (auto [to, cost] : g[v]) { if (to != par) { setik.insert(sub[to]); } } for (auto [to, cost] : g[v]) { if (to != par) { int opt = up; setik.erase(setik.find(sub[to])); if (!setik.empty()) { chmax(opt, *(--setik.end())); } setik.insert(sub[to]); calc_far(to, v, opt + cost); } } } signed main() { fastInp; cin >> n; for (int i = 1; i < n; i++) { cin >> A[i] >> B[i] >> C[i] >> D[i]; g[A[i]].pb({B[i], C[i]}); g[B[i]].pb({A[i], D[i]}); edge[{A[i], B[i]}] = i; edge[{B[i], A[i]}] = i; } cin >> q; for (int i = 1; i <= q; i++) { cin >> e[i]; } calc_t(1, -1); if (n <= 16) { brute_force(); } else { subtask3 = (q == 1 && e[1] == 2); used_id = 1; add(1, used_id); int sum_root = 0; int sum = 0; for (int i = 1; i < n; i++) { if (used[i][0] == used_id) { sum_root += C[i]; } if (used[i][1] == used_id) { sum_root += D[i]; } sum += C[i] + D[i]; } calc_sub(1, -1); calc_far(1, -1, 0); dfs(1, -1, sum_root); cout << sum - mx << endl; } }
#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...