Submission #839580

#	Time	Username	Problem	Language	Result	Execution time	Memory
839580		model_code	Truck Driver (IOI23_deliveries)	C++17	43 / 100	4532 ms	21748 KiB

deliveries

// time_limit/sol_vp_brute_force_reroot.cpp

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

using namespace std;

vector<vector<pair<int, long long>>> g;
vector<long long> weight, sz;
vector<int> up, height, cnt;
vector<bool> vis;

pair<int, int> dfs0(int x, int p, int d){
    vis[x] = true;
    up[x] = p;
    pair<int, int> res = {d, x};
    for(auto [y, w] : g[x]){
        if(!vis[y]){
            res = max(res, dfs0(y, x, d+1));
        }
    }
    return res;
}

void dfs(int x, int p, int w_ = 0){
    vis[x] = true;
    weight[x] = w_;
    up[x] = p;
    sz[x] = cnt[x];
    height[x] = 0;
    for(auto [y, w] : g[x]){
        if(!vis[y]){
            dfs(y, x, w);
            sz[x] += sz[y];
            height[x] = max(height[x], height[y] + 1);
        }
    }
}

long long weight_sum = 0;
int C;

void update(int x, int c){
    cnt[x] += c;
    while(x != -1){
        sz[x] += c;
        weight_sum += weight[x] * c;
        x = up[x];
    }
}

int get_c(int x, long long m){
    for(auto [y, w] : g[x]){
        if(up[y] == x && sz[y]*2 > m){
            weight_sum += (sz[x] - sz[y]*2) * weight[y];
            long long tmp = sz[x];
            sz[x] -= sz[y];
            sz[y] = tmp;
            up[x] = y;
            up[y] = -1;
            weight[x] = weight[y];
            weight[y] = 0;
            return get_c(y, m);
        }
    }
    C = x;
    return x;
}

void print(){
    for(int i = 0; i < (int)g.size(); i++){
        cout << "i: " << i << " sz: " << sz[i] << " w: " << weight[i] << " up: " << up[i] << " cnt: " << cnt[i] << endl;
    }
}

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

    vis.assign(N, false);
    int tmp = dfs0(0, -1, 0).second;
    vis.assign(N, false);
    auto [d, s] = dfs0(tmp, -1, 0);

    for(int i = 0; i < d/2; i++) s = up[s];

    vis.assign(N, false);
    dfs(s, -1);
    C = s;

    for(int i = 0; i < N; i++){
        weight_sum += sz[i] * weight[i];
    }

    // cout << "C: " << C << endl;
    // cout << "weight sum: " << weight_sum << endl;

    return;
}

long long max_time(int S, int X) {
    if(S == 0) X++;
	update(S, X - cnt[S]);

    get_c(C, sz[C]);

    // cout << "centroid: " << c << endl;
    // print();

    return weight_sum * 2;
}

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