Submission #864432

#	Time	Username	Problem	Language	Result	Execution time	Memory
864432		boris_mihov	Truck Driver (IOI23_deliveries)	C++17	0 / 100	69 ms	64404 KiB

deliveries

#include "deliveries.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;

int n;
llong sumAll;
struct SegmentTreeChildren
{
    struct Node
    {
        llong value;
        int idx;
        
        Node()
        {
            value = idx = 0;
        }

        Node(llong _value, int _idx)
        {
            value = _value;
            idx = _idx;
        }
    };

    Node tree[4*MAXN];
    std::vector <int> tour;
    Node cmp(Node left, Node right)
    {
        if (left.value > right.value)
        {
            return left;
        } else
        {
            return right;
        }
    }

    void build(int l, int r, int node, llong sumW[])
    {
        if (l == r)
        {
            tree[node].value = sumW[tour[l]];
            tree[node].idx = l;
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node, sumW);
        build(mid + 1, r, 2*node + 1, sumW);
        tree[node] = cmp(tree[2*node], tree[2*node + 1]);
    }

    void update(int l, int r, int node, int queryPos, llong queryVal)
    {
        if (l == r)
        {
            tree[node].value += queryVal;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
        else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
        tree[node] = cmp(tree[2*node], tree[2*node + 1]);
    }

    Node query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }    

        Node res = {0, 0};
        int mid = (l + r) / 2;
        if (queryL <= mid) res = cmp(res, query(l, mid, 2*node, queryL, queryR));
        if (mid + 1 <= queryR) res = cmp(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
        return res;
    }

    void build(llong sumW[], std::vector <int> _tour)
    {
        tour = _tour;
        build(0, tour.size() - 1, 1, sumW);
    }

    void update(int pos, llong value)
    {
        update(0, tour.size() - 1, 1, pos, value);
    }

    int query(int l, int r)
    {
        return query(0, tour.size() - 1, 1, l, r).idx;
    }
};

struct SegmentTree
{
    struct Node
    {
        llong maxSz;
        llong sumSzT;
        llong sumT;
        llong lazy;

        Node()
        {
            maxSz = sumSzT = sumT = lazy = 0;
        }

        Node(llong _maxSz, llong _sumSzT, llong _sumT, llong _lazy)
        {
            maxSz = _maxSz;
            sumSzT = _sumSzT;
            sumT = _sumT;
            lazy = _lazy;
        }
    };

    Node tree[4*MAXN];
    std::vector <int> tour;

    Node cmp(Node left, Node right)
    {
        Node res;
        res.sumT = left.sumT + right.sumT;
        res.sumSzT = left.sumSzT + right.sumSzT;
        res.maxSz = std::max(left.maxSz, right.maxSz);
        return res;
    }

    void push(int node, int l, int r)
    {
        if (tree[node].lazy == 0)
        {
            return;
        }

        tree[node].maxSz += tree[node].lazy;
        tree[node].sumSzT += tree[node].sumT * tree[node].lazy;
        if (l < r)
        {
            tree[2*node].lazy += tree[node].lazy;
            tree[2*node + 1].lazy += tree[node].lazy;
        }

        tree[node].lazy = 0;
    }

    void build(int l, int r, int node, llong sumW[], int t[])
    {
        if (l == r)
        {
            tree[node].sumT = t[tour[l]];
            tree[node].sumSzT = t[tour[l]] * sumW[tour[l]];
            tree[node].maxSz = sumW[tour[l]];
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node, sumW, t);
        build(mid + 1, r, 2*node + 1, sumW, t);
        tree[node] = cmp(tree[2*node], tree[2*node + 1]);
    }

    void update(int l, int r, int node, int queryL, int queryR, llong queryADD)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazy += queryADD;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        update(l, mid, 2*node, queryL, queryR, queryADD);
        update(mid + 1, r, 2*node + 1, queryL, queryR, queryADD);
        tree[node] = cmp(tree[2*node], tree[2*node + 1]);
    }

    Node query(int l, int r, int node, int queryL, int queryR)
    {
        push(node, l, r);
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        int mid = (l + r) / 2;
        Node res = {0, 0, 0, 0};
        if (queryL <= mid) res = cmp(res, query(l, mid, 2*node, queryL, queryR));
        if (mid + 1 <= queryR) res = cmp(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
        return res;
    }

    int search(int l, int r, int node, int queryL, int queryR, llong queryVal)
    {
        push(node, l, r);
        if (l == r)
        {
            if (tree[node].maxSz <= queryVal) return -1;
            return l;
        }

        int mid = (l + r) / 2;
        if (queryL <= l && r <= queryR)
        {
            if (tree[node].maxSz <= queryVal)
            {
                return -1;
            }

            push(2*node + 1, mid + 1, r);          
            if (tree[2*node + 1].maxSz > queryVal) return search(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
            else return search(l, mid, 2*node, queryL, queryR, queryVal);
        }

        if (mid + 1 <= queryR)
        {
            int res = search(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
            if (res != -1) return res;
        }

        return search(l, mid, 2*node, queryL, queryR, queryVal);
    }

    void build(llong sumW[], int t[], std::vector <int> _tour)
    {
        tour = _tour;
        build(0, tour.size() - 1, 1, sumW, t);
    }

    void update(int l, int r, llong value)
    {
        update(0, tour.size() - 1, 1, l, r, value);
    }

    llong querySZ(int idx)
    {
        return query(0, tour.size() - 1, 1, idx, idx).maxSz;
    }

    llong querySumT(int l, int r)
    {
        return query(0, tour.size() - 1, 1, l, r).sumT;
    }

    llong queryChange(int l, int r)
    {
        Node queryRes = query(0, tour.size() - 1, 1, l, r);
        llong res = sumAll * queryRes.sumT - 2 * queryRes.sumSzT;
        return res;
    }

    int search(int l, int r, llong value)
    {
        return search(0, tour.size() - 1, 1, l, r, value);
    }
};

int w[MAXN];
llong sumW[MAXN];
SegmentTree segTree;
SegmentTreeChildren segTreeChildren;
std::vector <std::pair <int,int>> g[MAXN];
std::vector <int> tour, tourChildren;
int inTourChildren[MAXN];
int lTourChildren[MAXN];
int rTourChildren[MAXN];
int parentEdge[MAXN];
int chainSize[MAXN];
int parent[MAXN];
int segPos[MAXN];
llong dist[MAXN];
int heavy[MAXN];
int head[MAXN];
int sz[MAXN];
llong sumD;

void initDFS(int node, int par)
{
    parent[node] = par;
    for (auto &p : g[node])
    {
        if (p.first == par)
        {
            parentEdge[node] = p.second;
            std::swap(p, g[node].back());
            g[node].pop_back();
            break;
        }    
    }

    lTourChildren[node] = tourChildren.size();
    for (const auto &[u, d] : g[node])
    {
        tourChildren.push_back(u);
        inTourChildren[u] = tourChildren.size() - 1;
    }

    rTourChildren[node] = tourChildren.size() - 1;

    sz[node] = 1;
    heavy[node] = 0;
    sumW[node] = w[node];
    for (const auto &[u, d] : g[node])
    {
        dist[u] = dist[node] + d;
        initDFS(u, node);

        sz[node] += sz[u];
        sumW[node] += sumW[u];
        if (sz[u] > sz[heavy[node]])
        {
            heavy[node] = u;
        }
    }
}

void buildChainsDFS(int node, int h)
{
    head[node] = h;
    tour.push_back(node);
    segPos[node] = tour.size() - 1;
    chainSize[head[node]]++;

    if (heavy[node] != 0)
    {
        buildChainsDFS(heavy[node], h);
    }

    for (const auto &[u, d] : g[node])
    {
        if (u != heavy[node])
        {
            buildChainsDFS(u, u);
        }
    }
}

void updateW(int node, int delta)
{  
    segTree.update(segPos[head[node]], segPos[node], delta);
    if (head[node] != 1)
    {
        segTreeChildren.update(inTourChildren[head[node]], delta);
        updateW(parent[head[node]], delta);
    }
}

llong rec(int node, llong currD)
{
    assert(head[node] == node);
    int search = segTree.search(segPos[head[node]], segPos[head[node]] + chainSize[head[node]] - 1, sumAll / 2);
    assert(search != -1);

    if (segPos[head[node]] < search)
    {
        currD += segTree.queryChange(segPos[head[node]] + 1, search);
    }

    node = tour[search];
    int child = segTreeChildren.query(lTourChildren[node], rTourChildren[node]);
    child = tourChildren[child];
    if (w[child] <= sumAll / 2)
    {
        return currD;
    } 

    currD += (sumAll - 2 * segTree.querySZ(segPos[child])) * parentEdge[child];
    return rec(child, currD); 
}

void init(int N, std::vector <int> U, std::vector <int> V, std::vector <int> T, std::vector <int> W)
{
    n = N;
    for (int i = 0 ; i < n - 1 ; ++i)
    {
        g[U[i] + 1].push_back({V[i] + 1, T[i]});
        g[V[i] + 1].push_back({U[i] + 1, T[i]});
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        w[i] = W[i - 1];
        sumAll += w[i];
    }

    w[1]++;
    sumAll++;

    initDFS(1, 0);
    for (int i = 1 ; i <= n ; ++i)
    {
        sumD += 1LL * dist[i] * w[i];
    }

    buildChainsDFS(1, 1);
    segTree.build(sumW, parentEdge, tour);
    segTreeChildren.build(sumW, tourChildren);
}

llong max_time(int S, int X) 
{
    S++;
    sumAll -= w[S];
    int oldValue = w[S];

    w[S] = X;
    if (S == 1) w[S]++;
    sumAll += w[S];

    sumD += 1LL * (w[S] - oldValue) * dist[S];
    updateW(S, w[S] - oldValue);
    return 2 * rec(1, sumD);
}

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