Submission #839567

#	Time	Username	Problem	Language	Result	Execution time	Memory
839567		model_code	Truck Driver (IOI23_deliveries)	C++17	29 / 100	4582 ms	21436 KiB

deliveries

// correct/solution-subtask2.cpp

#include "deliveries.h"

#include <iostream>
#include <vector>

#define MAXN 101000

using namespace std;

long long N, centroid, allSumW, ans;
vector<int> edge[MAXN];
long long W[MAXN];
long long sumW[MAXN];
long long T[MAXN];

bool dfs(int x){
    sumW[x] = W[x];
    bool flipped = false;
    for(int i : edge[x]){
        flipped |= dfs(i);
        sumW[x] += sumW[i];
    }

    if(centroid==-1 && sumW[x] >= (allSumW + 1)/2){
        centroid = x;
        flipped = true;
    }

    if(flipped){
        ans += (allSumW - sumW[x]) * T[x];
    } else {
        ans += sumW[x] * T[x];
    }

    return flipped;
}

void init(int NN, std::vector<int> UU, std::vector<int> VV, std::vector<int> TT, std::vector<int> WW){
	N = NN;
    vector<vector<pair<int,int>>> e(N);
	for (int i=0; i+1<N; ++i) {
		e[UU[i]].push_back({VV[i], TT[i]});
		e[VV[i]].push_back({UU[i], TT[i]});
	}
	vector<int> AA(N, -1), q = {0};
	vector<int> TTT(N, 0);
	for (int i = 0; i < (int)q.size(); ++i) {
		int u = q[i];
		for (auto [v, t] : e[u]) {
			if (AA[u] == v) continue;
			AA[v] = u;
			TTT[v] = t;
			q.push_back(v);
		}
	}

    for(int i=0; i<N-1; i++){
		edge[AA[i+1]].push_back(i+1);
        T[i+1] = TTT[i+1];
	}
	for(int i=0; i<N; i++){
		W[i] = WW[i];
	}
	W[0]++;

    for(int i=0; i<N; i++)
        allSumW += W[i];
}

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

    allSumW -= W[S];

	W[S] = X;
    allSumW += W[S];

    ans = 0; centroid = -1; dfs(0);
    return 2*ans;
}

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