Submission #839574

#	Time	Username	Problem	Language	Result	Execution time	Memory
839574		model_code	Truck Driver (IOI23_deliveries)	C++17	29 / 100	493 ms	61528 KiB

deliveries

// incorrect/sol_vp_fixed_guess2.cpp

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

using namespace std;

struct graph{
    vector<long long> dist;
    vector<int> cnt;
    long long weight_sum;
    int C;
};

vector<vector<pair<int, long long>>> g;
vector<int> ord, dist, under;
vector<bool> vis;
vector<graph> gds;

void dfs0(int x, int d){
    vis[x] = true;
    dist[x] = d;
    under[x] = 1;
    for(auto [y, w] : g[x]){
        if(!vis[y]){
            dfs0(y, d + 1);
            under[x] += under[y];
        }
    }
}

int get_c(int x, int p, int n){
    for(auto [y, w] : g[x]){
        if(y != p && under[y]*2 > n){
            return get_c(y, x, n);
        }
    }
    return x;
}

long long dfs(graph &gd, int x, long long d){
    vis[x] = true;
    gd.dist[x] = d;
    long long res = gd.cnt[x];
    for(auto [y, w] : g[x]){
        if(!vis[y]){
            long long tmp = dfs(gd, y, w + d);
            gd.weight_sum += w * tmp;
            res += tmp;
        }
    }
    return res;
}

void update(graph &gd, int x, int c){
    if(x == 0) ++c;
    gd.weight_sum += (c - gd.cnt[x]) * gd.dist[x];
    gd.cnt[x] = c;
}

void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
	g.resize(N);
    under.resize(N);
    dist.resize(N);
    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]);
    }
  
    // near centroid
    vis.assign(N, false);
    dfs0(0, 0);
    int c = get_c(0, -1, N);
    vis.assign(N, false);
    dfs0(c, 0);
    // end

    const int B = min(N, 5000000/N);

    mt19937 gen(42);
    ord.resize(N);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [](int a, int b) -> bool { return dist[a] < dist[b]; });
    ord.resize(B);

    gds.resize(B);

    W[0]++;
    for(int i = 0; i < B; i++){
        vis.assign(N, false);
        gds[i].C = ord[i];
        gds[i].weight_sum = 0;
        gds[i].dist.resize(N);
        gds[i].cnt = W;
        dfs(gds[i], ord[i], 0);
    }

    return;
}

long long max_time(int S, int X) {
    long long res = 1e18;
    for(int i = 0; i < (int)gds.size(); i++){
        update(gds[i], S, X);
        res = min(res, gds[i].weight_sum);
        // cout << "i: " << i << ' ' << gds[i].weight_sum << endl;
    }
    return res * 2;
}

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