Submission #1072544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072544		jerzyk	Truck Driver (IOI23_deliveries)	C++17	100 / 100	1912 ms	50152 KiB

deliveries

#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;
}

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 36 / 36