Submission #1072544

#TimeUsernameProblemLanguageResultExecution timeMemory
1072544jerzykTruck Driver (IOI23_deliveries)C++17
100 / 100
1912 ms50152 KiB
#include <bits/stdc++.h> #include "deliveries.h" using namespace std; #define pb push_back #define st first #define nd second typedef long long ll; typedef long double ld; const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL; const int II = 2 * 1000 * 1000 * 1000; const ll M = 1000LL * 1000LL * 1000LL + 7LL; const int N = 1<<17; int n; ll tab[N], sum[N], pth[N]; ll al = 0LL; vector<pair<int, ll>> ed[N]; bool vis[N]; int cnt = 0, clrcnt = 0; int pos[N], revp[N], frs[N], sp[N], oj[N], il[N]; ll drzs[2 * N], dod[2 * N], l1[2 * N]; ll drzc[2 * N], l2[2 * N]; inline void PushC(int v) { drzc[v * 2] += l2[v]; l2[v * 2] += l2[v]; drzc[v * 2 + 1] += l2[v]; l2[v * 2 + 1] += l2[v]; l2[v] = 0; } void AddC(int v, int p, int k, int pz, int kz, ll x) { if(p > kz || k < pz) return; if(p >= pz && k <= kz) { drzc[v] += x; l2[v] += x; return; } AddC(v * 2, p, (p + k) / 2, pz, kz, x); AddC(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x); drzc[v] = max(drzc[v * 2], drzc[v * 2 + 1]) + l2[v]; } int FindC(ll x) { int v = 1; while(v < N) { PushC(v); v *= 2; ++v; if(drzc[v] < x) --v; } return v - N; } inline void PushS(int v) { drzs[v * 2] += dod[v * 2] * l1[v]; l1[v * 2] += l1[v]; drzs[v * 2 + 1] += dod[v * 2 + 1] * l1[v]; l1[v * 2 + 1] += l1[v]; l1[v] = 0LL; } void AddS(int v, int p, int k, int pz, int kz, ll x) { if(p > kz || k < pz) return; if(p >= pz && k <= kz) { drzs[v] += dod[v] * x; l1[v] += x; return; } PushS(v); AddS(v * 2, p, (p + k) / 2, pz, kz, x); AddS(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x); drzs[v] = drzs[v * 2] + drzs[v * 2 + 1]; } ll QueryS(int v, int p, int k, int pz, int kz) { if(p > kz || k < pz) return 0LL; if(p >= pz && k <= kz) return drzs[v]; ll ans; PushS(v); ans = QueryS(v * 2, p, (p + k) / 2, pz, kz); ans += QueryS(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz); return ans; } void DFS(int v) { vis[v] = true; sum[v] = tab[v]; il[v] = 1; for(int i = 0; i < (int)ed[v].size(); ++i) { if(vis[ed[v][i].st]) continue; pth[ed[v][i].st] = pth[v] + ed[v][i].nd; oj[ed[v][i].st] = v; DFS(ed[v][i].st); sum[v] += sum[ed[v][i].st]; il[v] += il[ed[v][i].st]; } //cerr << answer << " dfs: " << v - 1 << " " << sum[v] << " " << al << " " << ev << "\n"; vis[v] = false; } void DFSH(int v, int clr, ll ev) { drzs[pos[v] + N] = ev * sum[v]; dod[pos[v] + N] = ev; drzc[pos[v] + N] = sum[v]; //cerr << "HLD " << v << " " << clr << " " << pos[v] << " " << ev << " " << sum[v] << "\n"; revp[pos[v]] = v; pair<int, int> ma = make_pair(-1, -1); sp[v] = clr; for(int i = 0; i < (int)ed[v].size(); ++i) if(sp[ed[v][i].st] == 0) ma = max(ma, make_pair(il[ed[v][i].st], i)); if(ma == make_pair(-1, -1)) return; int ne = ed[v][ma.nd].st; pos[ne] = pos[v] + 1; ++cnt; DFSH(ne, clr, ed[v][ma.nd].nd); for(int i = 0; i < (int)ed[v].size(); ++i) { int ne = ed[v][i].st; if(sp[ne]) continue; ++clrcnt; ++cnt; pos[ne] = cnt; frs[clrcnt] = ne; DFSH(ne, clrcnt, ed[v][i].nd); } } void HLDChange(int v, ll x) { while(v > 0) { int a = pos[frs[sp[v]]], b = pos[v]; AddC(1, 0, N - 1, a, b, x); AddS(1, 0, N - 1, a, b, x); v = oj[frs[sp[v]]]; } } ll HLDQuery(int v) { ll s = 0LL; while(v > 0) { int a = pos[frs[sp[v]]], b = pos[v]; s += QueryS(1, 0, N - 1, a, b); v = oj[frs[sp[v]]]; } return s; } void InitTrees() { for(int v = N - 1; v >= 1; --v) { drzc[v] = max(drzc[v * 2], drzc[v * 2 + 1]); drzs[v] = drzs[v * 2] + drzs[v * 2 + 1]; dod[v] = dod[v * 2] + dod[v * 2 + 1]; } } void init(int _N, vector<int> U, vector<int> V, vector<int> T, vector<int> W) { n = _N; for(int i = 1; i <= n; ++i) tab[i] = W[i - 1]; tab[1] += 1LL; for(int i = 1; i <= n; ++i) al += tab[i]; for(int i = 0; i < n - 1; ++i) { ed[U[i] + 1].pb(make_pair(V[i] + 1, (ll)T[i])); ed[V[i] + 1].pb(make_pair(U[i] + 1, (ll)T[i])); } oj[1] = 1; DFS(1); cnt = 1; clrcnt = 1; pos[1] = 1; frs[1] = 1; DFSH(1, 1, 0LL); oj[1] = 0; InitTrees(); //cerr << "After Init " << drzs[1] << "\n"; } long long max_time(int S, int X) { ++S; if(S == 1) ++X; ll ch = X - tab[S]; tab[S] += ch; al += ch; HLDChange(S, ch); ll answer = drzs[1]; //cout << "Beg " << answer << "\n"; int cen = revp[FindC((al + 1LL) / 2LL)]; //cout << "centroid " << cen << "\n"; answer -= 2LL * HLDQuery(cen); answer += pth[cen] * al; //cerr << "nquery\n"; return answer * 2LL; }
#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...