Submission #839575

#	Time	Username	Problem	Language	Result	Execution time	Memory
839575		model_code	Truck Driver (IOI23_deliveries)	C++17	8 / 100	103 ms	7712 KiB

deliveries

// incorrect/sol_vp_fixed_guess.cpp

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

using namespace std;

vector<vector<pair<int, long long>>> g;
vector<long long> dist;
vector<int> cnt;
vector<bool> vis;
priority_queue<pair<int, int>> pq;


long long weight_sum = 0;
int C;

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

void update(int x, int c){
    int tmp = cnt[x];
    cnt[x] = c;
    pq.push({cnt[x], x});
    while(cnt[pq.top().second] != pq.top().first) pq.pop();
    if(pq.top().second != C){
        C = pq.top().second;
        weight_sum = 0;
        vis.assign(g.size(), false);
        dfs(C, 0);
    } else {
        weight_sum += (c - tmp) * dist[x];
    }
}

void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
	g.resize(N);
    dist.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]);
    }

    for(int i = 0; i < N; i++){
        pq.push({cnt[i], i});
    }

    weight_sum = 0;
    vis.assign(N, false);
    dfs(0, 0);

    return;
}

long long max_time(int S, int X) {
    if(S == 0) X++;
	update(S, X);
    // cout << "centroid: " << C << endl;

    return weight_sum * 2;
}

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