oj.uz

Submission #839572

# Submission time Handle Problem Language Result Execution time Memory
839572 2023-08-30T08:59:55 Z model_code Truck Driver (IOI23_deliveries) C++17
22 / 100
 251 ms 18908 KB 
// 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 10004 KB Output is correct
2 Correct 76 ms 9804 KB Output is correct
3 Correct 73 ms 10016 KB Output is correct
4 Correct 93 ms 9948 KB Output is correct
5 Correct 80 ms 10128 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB 3rd lines differ - on the 1st token, expected: '1627540', found: '323344'
2 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 10004 KB Output is correct
2 Correct 76 ms 9804 KB Output is correct
3 Correct 73 ms 10016 KB Output is correct
4 Correct 93 ms 9948 KB Output is correct
5 Correct 80 ms 10128 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 20 ms 4308 KB Output is correct
9 Correct 207 ms 17500 KB Output is correct
10 Correct 251 ms 17520 KB Output is correct
11 Correct 191 ms 17496 KB Output is correct
12 Correct 132 ms 18908 KB Output is correct
13 Correct 130 ms 18844 KB Output is correct
14 Correct 136 ms 18840 KB Output is correct

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 10004 KB Output is correct
2 Correct 76 ms 9804 KB Output is correct
3 Correct 73 ms 10016 KB Output is correct
4 Correct 93 ms 9948 KB Output is correct
5 Correct 80 ms 10128 KB Output is correct
6 Incorrect 1 ms 2644 KB 3rd lines differ - on the 1st token, expected: '129238', found: '30876'
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 10004 KB Output is correct
2 Correct 76 ms 9804 KB Output is correct
3 Correct 73 ms 10016 KB Output is correct
4 Correct 93 ms 9948 KB Output is correct
5 Correct 80 ms 10128 KB Output is correct
6 Incorrect 2 ms 2644 KB 3rd lines differ - on the 1st token, expected: '1627540', found: '323344'
7 Halted 0 ms 0 KB -