Submission #839579

#	Time	Username	Problem	Language	Result	Execution time	Memory
839579		model_code	Truck Driver (IOI23_deliveries)	C++17	43 / 100	4527 ms	381848 KiB

deliveries

// time_limit/sol_vp_brute_force2.cpp

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

using namespace std;

struct node{
    int x, upd;
    long long w;
    bool operator<(const node& n) const{
        if(w != n.w) return w < n.w;
        return x < n.x;
    }
};

vector<vector<pair<int, long long>>> g;
vector<priority_queue<node>> g2;
vector<long long> weight, sz;
vector<int> up, height, cnt, upd;
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);
            g2[x].push(node{y, 0, sz[y]});
        }
    }
}

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;
        
        upd[x]++;
        if(up[x] != -1){
            g2[up[x]].push(node{x, upd[x], sz[x]});
        }
        x = up[x];
    }
}

int get_c(int x, long long m){
    while(!g2[x].empty() && g2[x].top().upd != upd[g2[x].top().x]) g2[x].pop();
    return !g2[x].empty() && sz[g2[x].top().x]*2 > m ? get_c(g2[x].top().x, m) : 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);
    g2.resize(N);
    upd.assign(N, 0);
    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]);

    int c = get_c(C, sz[C]);

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

    long long res = weight_sum;
    while(c != -1){
        res += (sz[C] - sz[c] * 2) * weight[c];
        c = up[c];
    }

    return res * 2;
}

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