Submission #839572

#	Time	Username	Problem	Language	Result	Execution time	Memory
839572		model_code	Truck Driver (IOI23_deliveries)	C++17	22 / 100	251 ms	18908 KiB

deliveries

// correct/solution-subtask3.cpp

#include "deliveries.h"

#include <iostream>
#include <vector>

#define MAXN 101000

using namespace std;

long long N, centroid, allSumW, allSumTxW, flippedWT;
vector<int> edge[MAXN];
long long W[MAXN];
long long sumW[MAXN];
long long T[MAXN];
long long sumT[MAXN];
long long parent[MAXN];

void dfs(int x){
    sumW[x] = W[x];
    for(int i : edge[x]){
        sumT[i] = sumT[x] + T[i];
        dfs(i);
        sumW[x] += sumW[i];
    }
}

int findCentroid(int x){
    for(int i:edge[x]){
        if(sumW[i] >= (allSumW + 1) / 2){
            flippedWT += T[i] * sumW[i];
            return findCentroid(i);
        }
    }
    return x;
}

void init(int NN, std::vector<int> /*UU*/, std::vector<int> /*VV*/, std::vector<int> TT, std::vector<int> WW){
	N = NN;
    parent[0] = -1;
    for(int i=0; i<N-1; i++){
		edge[i/2].push_back(i+1);
        T[i+1] = TT[i];
        parent[i+1] = i/2;
	}
	for(int i=0; i<N; i++){
		W[i] = WW[i];
	}
	W[0]++;

    dfs(0);

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

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

    long long diff = X - W[S];
    allSumTxW += diff * sumT[S];
    allSumW -= W[S];

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

    while(S!=-1){
        sumW[S] += diff;
        S = parent[S];
    }

    flippedWT = 0;
    int cent = findCentroid(0);

    return 2 * (allSumTxW + allSumW * sumT[cent] - 2 * flippedWT);
}

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