oj.uz

Submission #839565

# Submission time Handle Problem Language Result Execution time Memory
839565 2023-08-30T08:59:37 Z model_code Truck Driver (IOI23_deliveries) C++17
100 / 100
 839 ms 55144 KB 
// model_solution/solution.cpp

#include "deliveries.h"

#include <vector>
#include <set>
#include <iostream>

#define MAXN 101000

using namespace std;

long long N, allSumTxW, allSumW, segId, uFrom, uValue, flippedWT;
vector<int> edge[MAXN];
long long W[MAXN];
long long T[MAXN];
int parent[MAXN];
int num[MAXN];
long long sumT[MAXN];
bool heavy[MAXN];
int seg[MAXN];
int segPos[MAXN];
vector<int> segNodes[MAXN];
int nodes[MAXN];
int segParent[MAXN];
long long sumW[MAXN];
set<pair<long long, int>> maxSumW[MAXN];

struct node{
	int id, a, b;
	long long w, l, sumWT, sumL, sumT;
	node* leftC;
	node* rightC;
};
node* trees[MAXN];

node* build(int x, int y){
	node* p = new node;
	node* lc = nullptr;
	node* rc = nullptr;

	p->a = x; p->b = y; p->id = -1; p->l = 0;
	p->sumWT = 0; p->sumL = 0; p->sumT = 0;
	if(x==y){
		p->id = nodes[x-1];
		p->w = sumW[p->id];
		p->sumT = T[p->id];
		p->sumWT = p->sumT * sumW[p->id];
	} else {
		lc = build(x,(x+y)/2);
		rc = build((x+y)/2+1,y);
		p->w = rc->w;
		p->sumWT = lc->sumWT + rc->sumWT;
		p->sumT = lc->sumT + rc->sumT;
	}
	p->leftC = lc; p->rightC = rc;
	return p;
}

long long value(node* p){
	return p->w+p->l;
}
long long sumValue(node* p){
	return p->sumWT + p->sumL * p->sumT;
}
void push_down(node* p){
	(p->leftC)->l += p->l;
	(p->rightC)->l += p->l;
	p->l = 0;
	(p->leftC)->sumL += p->sumL;
	(p->rightC)->sumL += p->sumL;
	p->sumL = 0;
}
void update_node(node* p){
	p->w = value(p->rightC);
	p->sumWT = sumValue(p->leftC) + sumValue(p->rightC);
}

void update(node* p){
	if(uFrom <= p->a){
		p->l += uValue;
		p->sumL += uValue;
		return;
	}

	push_down(p);

	if(uFrom <= (p->a+p->b)/2)
		update(p->leftC);
	update(p->rightC);

	update_node(p);
}

int findC(node* p){
	if(p->a==p->b){
		flippedWT += sumValue(p);
		return p->id;
	}

	push_down(p);
	update_node(p);

	if(value(p->leftC) >= (allSumW + 1)/2){
		flippedWT += sumValue(p->rightC);
		return findC(p->leftC);
	}
	return findC(p->rightC);
}

void preDfs(int x){
	allSumW += W[x];
	allSumTxW += sumT[x] * W[x];
	sumW[x] = W[x];
	num[x] = 1;
	for(int i:edge[x]){
		parent[i] = x;
		sumT[i] = sumT[x] + T[i];
		preDfs(i);
		num[x] += num[i];
		sumW[x] += sumW[i];
	}
}

void dfs(int x){
	for(int i:edge[x]){
		dfs(i);
	}
	heavy[x] = (x != 0 && num[x] >= (num[parent[x]]+1)/2);
	if(seg[x]==-1)
		seg[x] = segId++;
	if(heavy[x]){
		seg[parent[x]] = seg[x];
	} else if(x!=0){
		maxSumW[parent[x]].insert({sumW[x],seg[x]});
		segParent[seg[x]] = parent[x];
	}
	segNodes[seg[x]].push_back(x);
	segPos[x] = segNodes[seg[x]].size();
}

void build_trees(){
	for(int i=0; i<segId; i++){
		int count = 0;
		for(int j:segNodes[i])
			nodes[count++] = j;
		trees[i] = build(1,count);
	}
}

void updateLine(int x, long long diff){
	uValue = diff;
	while(x!=-1){
		int sx = seg[x], px = segParent[sx];

		if(px!=-1)
			maxSumW[px].erase({value(trees[sx]),sx});

		uFrom = segPos[x];
		update(trees[sx]);
		
		if(px!=-1)
			maxSumW[px].insert({value(trees[sx]),sx});
		
		x = px;
	}
}

int findCentroid(int sx){
	int c = findC(trees[sx]);
	auto it = maxSumW[c].end();
	if(it!=maxSumW[c].begin()){
		it--;
		if((*it).first >= (allSumW+1)/2){
			return findCentroid((*it).second);
		}
	}
	return c;
}

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];
		seg[i] = -1;
		segParent[i] = -1;
	}

	W[0]++;
	parent[0] = -1;
	preDfs(0); dfs(0);
	build_trees();
}

long long max_time(int S, int X) {
	if(S==0) X++;
	long long diff = X - W[S];
	W[S] = X;
	allSumTxW += diff * sumT[S];
	allSumW += diff;

	updateLine(S, diff);

	flippedWT = 0;
	int c = findCentroid(seg[0]);

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 17128 KB Output is correct
2 Correct 94 ms 17004 KB Output is correct
3 Correct 80 ms 17236 KB Output is correct
4 Correct 86 ms 17080 KB Output is correct
5 Correct 81 ms 17212 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9812 KB Output is correct
2 Correct 5 ms 10068 KB Output is correct
3 Correct 7 ms 10120 KB Output is correct
4 Correct 6 ms 10196 KB Output is correct
5 Correct 8 ms 10196 KB Output is correct
6 Correct 6 ms 10196 KB Output is correct
7 Correct 7 ms 10196 KB Output is correct
8 Correct 6 ms 10196 KB Output is correct
9 Correct 6 ms 10196 KB Output is correct
10 Correct 6 ms 10168 KB Output is correct
11 Correct 8 ms 10192 KB Output is correct
12 Correct 6 ms 10196 KB Output is correct
13 Correct 7 ms 10196 KB Output is correct
14 Correct 6 ms 10196 KB Output is correct
15 Correct 5 ms 10196 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 17128 KB Output is correct
2 Correct 94 ms 17004 KB Output is correct
3 Correct 80 ms 17236 KB Output is correct
4 Correct 86 ms 17080 KB Output is correct
5 Correct 81 ms 17212 KB Output is correct
6 Correct 5 ms 9812 KB Output is correct
7 Correct 7 ms 10196 KB Output is correct
8 Correct 47 ms 13780 KB Output is correct
9 Correct 691 ms 47832 KB Output is correct
10 Correct 631 ms 47828 KB Output is correct
11 Correct 664 ms 47828 KB Output is correct
12 Correct 753 ms 49236 KB Output is correct
13 Correct 839 ms 49240 KB Output is correct
14 Correct 833 ms 49160 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 17128 KB Output is correct
2 Correct 94 ms 17004 KB Output is correct
3 Correct 80 ms 17236 KB Output is correct
4 Correct 86 ms 17080 KB Output is correct
5 Correct 81 ms 17212 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 8 ms 10196 KB Output is correct
8 Correct 40 ms 14344 KB Output is correct
9 Correct 310 ms 54524 KB Output is correct
10 Correct 275 ms 54548 KB Output is correct
11 Correct 344 ms 54448 KB Output is correct
12 Correct 323 ms 55088 KB Output is correct
13 Correct 494 ms 55144 KB Output is correct
14 Correct 311 ms 54548 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 17128 KB Output is correct
2 Correct 94 ms 17004 KB Output is correct
3 Correct 80 ms 17236 KB Output is correct
4 Correct 86 ms 17080 KB Output is correct
5 Correct 81 ms 17212 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 5 ms 10068 KB Output is correct
8 Correct 7 ms 10120 KB Output is correct
9 Correct 6 ms 10196 KB Output is correct
10 Correct 8 ms 10196 KB Output is correct
11 Correct 6 ms 10196 KB Output is correct
12 Correct 7 ms 10196 KB Output is correct
13 Correct 6 ms 10196 KB Output is correct
14 Correct 6 ms 10196 KB Output is correct
15 Correct 6 ms 10168 KB Output is correct
16 Correct 8 ms 10192 KB Output is correct
17 Correct 6 ms 10196 KB Output is correct
18 Correct 7 ms 10196 KB Output is correct
19 Correct 6 ms 10196 KB Output is correct
20 Correct 5 ms 10196 KB Output is correct
21 Correct 5 ms 9812 KB Output is correct
22 Correct 7 ms 10196 KB Output is correct
23 Correct 47 ms 13780 KB Output is correct
24 Correct 691 ms 47832 KB Output is correct
25 Correct 631 ms 47828 KB Output is correct
26 Correct 664 ms 47828 KB Output is correct
27 Correct 753 ms 49236 KB Output is correct
28 Correct 839 ms 49240 KB Output is correct
29 Correct 833 ms 49160 KB Output is correct
30 Correct 6 ms 9812 KB Output is correct
31 Correct 8 ms 10196 KB Output is correct
32 Correct 40 ms 14344 KB Output is correct
33 Correct 310 ms 54524 KB Output is correct
34 Correct 275 ms 54548 KB Output is correct
35 Correct 344 ms 54448 KB Output is correct
36 Correct 323 ms 55088 KB Output is correct
37 Correct 494 ms 55144 KB Output is correct
38 Correct 311 ms 54548 KB Output is correct
39 Correct 6 ms 9808 KB Output is correct
40 Correct 7 ms 10196 KB Output is correct
41 Correct 47 ms 14172 KB Output is correct
42 Correct 381 ms 51504 KB Output is correct
43 Correct 346 ms 52368 KB Output is correct
44 Correct 416 ms 53224 KB Output is correct
45 Correct 387 ms 52888 KB Output is correct
46 Correct 338 ms 53692 KB Output is correct
47 Correct 397 ms 53028 KB Output is correct
48 Correct 344 ms 53848 KB Output is correct
49 Correct 314 ms 54756 KB Output is correct
50 Correct 322 ms 53240 KB Output is correct
51 Correct 322 ms 54016 KB Output is correct
52 Correct 529 ms 48276 KB Output is correct
53 Correct 524 ms 48272 KB Output is correct
54 Correct 540 ms 48244 KB Output is correct
55 Correct 316 ms 54396 KB Output is correct
56 Correct 271 ms 55020 KB Output is correct
57 Correct 296 ms 54916 KB Output is correct