Submission #1109697

#TimeUsernameProblemLanguageResultExecution timeMemory
1109697_callmelucianDesignated Cities (JOI19_designated_cities)C++14
39 / 100
1805 ms59464 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pl; typedef pair<int,int> pii; typedef tuple<int,int,int> tpl; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) const int mn = 2e5 + 5; const auto start = chrono::high_resolution_clock::now(); const double TL = 1.8; double getTime() { auto cur = chrono::high_resolution_clock::now(); chrono::duration<double> elapsed = cur - start; return elapsed.count(); } struct IT { vector<pl> tr; vector<ll> lazy; IT (int sz) : tr(4 * sz), lazy(4 * sz) {} void apply (int k, ll val) { tr[k].first += val, lazy[k] += val; } void pushDown (int k) { if (lazy[k]) apply(2 * k, lazy[k]), apply(2 * k + 1, lazy[k]), lazy[k] = 0; } void build (int k, int l, int r, vector<pl> &a) { if (l == r) return tr[k] = a[l], void(); int mid = (l + r) >> 1; build(2 * k, l, mid, a); build(2 * k + 1, mid + 1, r, a); tr[k] = max(tr[2 * k], tr[2 * k + 1]); } void update (int a, int b, ll val, int k, int l, int r) { if (b < l || r < a) return; if (l == r) return apply(k, val), void(); pushDown(k); int mid = (l + r) >> 1; update(a, b, val, 2 * k, l, mid); update(a, b, val, 2 * k + 1, mid + 1, r); tr[k] = max(tr[2 * k], tr[2 * k + 1]); } pl getBest() { return tr[1]; } }; vector<tpl> adj[mn]; ll ans[mn], n; namespace originalTree { int bestLeaf[mn], secLeaf[mn]; ll downPath[mn], upPath[mn], sumDown; void dfs (int u, int p, int pA, int pH) { // construct costs on paths downPath[u] = downPath[p] + pA; upPath[u] = upPath[p] + pH; bestLeaf[u] = u; // run dfs down for (tpl item : adj[u]) { int v, away, home; tie(v, away, home) = item; if (v == p) continue; dfs(v, u, away, home); sumDown += away; if (downPath[bestLeaf[v]] > downPath[bestLeaf[u]]) secLeaf[u] = bestLeaf[u], bestLeaf[u] = bestLeaf[v]; else if (downPath[bestLeaf[v]] > downPath[secLeaf[u]]) secLeaf[u] = bestLeaf[v]; } } ll tryNode (int u) { ll pathOne = downPath[bestLeaf[u]] - (bestLeaf[u] ? downPath[u] : 0); ll pathTwo = downPath[secLeaf[u]] - (secLeaf[u] ? downPath[u] : 0); return sumDown - pathOne - pathTwo - downPath[u] + upPath[u]; } ll chooseNode (int u) { return sumDown - downPath[u] + upPath[u]; } } namespace modifiedTree { int num[mn], sz[mn], up[mn], toP[mn], timeDfs; bool colored[mn]; ll weight[mn]; IT tree(mn); bool dfs (int u, int p, int y, int w) { num[u] = ++timeDfs, sz[u] = 1, up[u] = p, toP[u] = w; if (u == y) colored[u] = 1; for (tpl item : adj[u]) { int v, away, home; tie(v, away, home) = item; if (v == p) continue; if (dfs(v, u, y, away)) colored[u] = 1; sz[u] += sz[v]; } return colored[u]; } void buildTree() { vector<pl> a(n + 1); for (int i = 1; i <= n; i++) a[num[i]] = make_pair(0, i); for (int i = 1; i <= n; i++) { int u = a[i].second; if (!colored[u]) a[i].first = weight[u] = weight[up[u]] + toP[u]; } tree.build(1, 1, n, a); } void colorNode (int u) { if (!u) return; while (!colored[u]) { tree.update(num[u], num[u] + sz[u] - 1, -toP[u], 1, 1, n); colored[u] = 1, u = up[u]; if (getTime() > TL) { cout << "Still don't know why did I got TLE\n"; exit(0); } } } }; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i < n; i++) { int a, b, c, d; cin >> a >> b >> c >> d; adj[a].emplace_back(b, c, d); adj[b].emplace_back(a, d, c); } originalTree::dfs(1, 1, 0, 0); for (int i = 1; i <= n; i++) ans[i] = LLONG_MAX; int optX = 0, optY = 0; for (int i = 1; i <= n; i++) { ll cur = originalTree::tryNode(i); if (cur < ans[2]) ans[2] = cur, optX = originalTree::bestLeaf[i], optY = originalTree::secLeaf[i]; ans[1] = min(ans[1], originalTree::chooseNode(i)); } modifiedTree::dfs(optX, optX, optY, 0); modifiedTree::buildTree(); bool leafLeft = 1; for (int i = 3; i <= n; i++) { if (leafLeft) { ll delta; int node; tie(delta, node) = modifiedTree::tree.getBest(); ans[i] = ans[i - 1] - delta; if (!delta) leafLeft = 0; modifiedTree::colorNode(node); } else ans[i] = ans[i - 1]; } int q; cin >> q; while (q--) { int E; cin >> E; cout << ans[E] << "\n"; } 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...