Submission #839578

#	Time	Username	Problem	Language	Result	Execution time	Memory
839578		model_code	Truck Driver (IOI23_deliveries)	C++17	29 / 100	4610 ms	131796 KiB

deliveries

// time_limit/sol_vp_sqrt.cpp

#include "deliveries.h"
#include <vector>
#include <iostream>

using namespace std;

const int B = 150;

struct node{
    vector<pair<int, long long>> edges;
    vector<int> edges_big;
    bool used = false;
    int cnt = 0, up = 0, up_big = 0;
    long long sz = 0, sz_big = 0, w = 0, w_big = 0, weight_sum = 0;
};

vector<node> g;
vector<int> big_nodes;

// LCA
vector<pair<long long, int>> tour;
vector<vector<pair<long long, int>>> st;
vector<long long> dist;
vector<int> in, out;

void lca_dfs(int x, int p, long long d){
    in[x] = (int)tour.size();
    dist[x] = d;
    tour.emplace_back(d, x);
    for(auto [y, w] : g[x].edges){
        if(y != p){
            lca_dfs(y, x, d + w);
        }
        tour.emplace_back(d, x);
    }
    out[x] = (int)tour.size() - 1;
}

void build_lca(){
    st.assign(tour.size(), vector<pair<long long, int>>(18));
    for(int i = 0; i < (int)tour.size(); i++) st[i][0] = tour[i];
    for(int j = 1; j < 18; j++){
        for(int i = 0; i < (int)tour.size() - (1<<(j-1)); i++){
            st[i][j] = min(st[i][j-1], st[i + (1<<(j-1))][j-1]);
        }
    }
}

int get_lca(int a, int b){
    int l = min(in[a], in[b]), r = max(out[a], out[b]);
    int bit = 31 - __builtin_clz(r - l + 1);
    return min(st[l][bit], st[r-(1<<bit)+1][bit]).second;
}

long long get_dist(int a, int b){
    return dist[a] + dist[b] - dist[get_lca(a, b)]*2;
}
// END

int dfs0(int x, int p){
    int res = 1;
    for(auto [y, w] : g[x].edges){
        if(y != p){
            res += dfs0(y, x);
        }
    }
    if(res > B){
        g[x].used = true;
        res = 1;
    }
    return res;
}

void dfs1(int x, int p, int p_big, long long w, long long w_big){
    g[x].up = p;
    g[x].up_big = p_big;
    g[x].w = w;
    g[x].w_big = w_big;
    g[x].sz = g[x].cnt;
    if(g[x].used){
        if(g[x].up_big != -1){
            g[g[x].up_big].edges_big.push_back(x);
        }
        p_big = x;
        w_big = 0;
    }
    for(auto [y, c] : g[x].edges){
        if(y != p){
            dfs1(y, x, p_big, c, w_big + c);
            g[x].sz += g[y].sz;
        }
    }
    g[x].sz_big = g[x].sz;
}

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

    W[0]++; //set 0

    // LCA:
    dist.resize(N);
    in.resize(N);
    out.resize(N);
    lca_dfs(0, -1, 0);
    build_lca();

    // set up cnt
    for(int i = 0; i < N; i++){
        g[i].cnt = W[i];
    }
    dfs0(0, -1);
    g[0].used = true; //root
    dfs1(0, -1, -1, 0, 0);

    for(int i = 0; i < N; i++){
        if(g[i].used){
            big_nodes.push_back(i);
        }
    }

    for(int x : big_nodes){
        for(int i = 0; i < N; i++){
            long long d = get_dist(x, i);
            g[x].weight_sum += d * g[i].cnt;
        }
    }

    return;
}

void update(int x, long long c){
    for(int y : big_nodes){
        long long d = get_dist(x, y);
        g[y].weight_sum += d * (c - g[x].cnt);
    }
    int y = g[x].used ? x : g[x].up_big;
    while(y != -1){
        g[y].sz_big += c - g[x].cnt;
        y = g[y].up_big;
    }
    g[x].cnt = c;
}

int get_c_big(int x){
    for(int y : g[x].edges_big){
        if(g[y].sz_big*2 > g[0].sz_big){
            return get_c_big(y);
        }
    }
    return x;
}

long long sz_dfs(int x, int p){
    if(g[x].used) return g[x].sz_big; //unset used on root
    g[x].sz = g[x].cnt;
    for(auto [y, w] : g[x].edges){
        if(y != p){
            g[x].sz += sz_dfs(y, x);
        }
    }
    return g[x].sz;
}

int get_c(int x, int p){
    for(auto [y, w] : g[x].edges){
        if(y != p && !g[y].used && g[y].sz*2 >= g[0].sz_big){
            return get_c(y, x);
        }
    }
    return x;
}

long long max_time(int S, int X) {
    if(S == 0) X++;
    update(S, X);

    if(g[0].sz_big == 0){
        return 0;
    }

    int C = get_c_big(0);
    g[C].used = false;
    sz_dfs(C, g[C].up);
    g[C].used = true;

    int c = get_c(C, g[C].up);

    long long res = g[C].weight_sum;
    while(c != C){
        res += (g[0].sz_big - g[c].sz * 2) * g[c].w;
        c = g[c].up;
    }

	return res * 2;
}

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