oj.uz

Submission #953984

# Submission time Handle Problem Language Result Execution time Memory
953984 2024-03-27T03:47:44 Z pcc Truck Driver (IOI23_deliveries) C++17
29 / 100
 5500 ms 19760 KB 
#include "deliveries.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long
#define pll pair<ll,ll>

const int mxn = 1e5+10;
vector<pii> tree[mxn];
ll W[mxn],sz[mxn],dep[mxn];

void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> t, std::vector<int> w) {
	for(int i = 0;i<N-1;i++){
		int a = U[i],b = V[i],c = t[i];
		tree[a].push_back(pll(b,c));
		tree[b].push_back(pll(a,c));
	}
	for(int i = 0;i<N;i++)W[i] = w[i];
	W[0] += 1;
	return;
}

void szdfs(int now,int par){
	sz[now] = W[now];
	for(auto nxt:tree[now]){
		if(nxt.fs == par)continue;
		szdfs(nxt.fs,now);
		sz[now] += sz[nxt.fs];
	}
	return;
}

int find_centroid(int now,int par,int tar){
	for(auto nxt:tree[now]){
		if(nxt.fs == par)continue;
		if(sz[nxt.fs]>tar)return find_centroid(nxt.fs,now,tar);
	}
	return now;
}

ll dfs1(int now,int par){
	ll re = 0;
	re += W[now]*dep[now];
	for(auto nxt:tree[now]){
		if(nxt.fs == par)continue;
		dep[nxt.fs] = dep[now]+nxt.sc;
		re += dfs1(nxt.fs,now);
	}
	return re;
}

long long max_time(int S, int X) {
	if(!S)X += 1;
	W[S] = X;
	szdfs(0,0);
	int cen = find_centroid(0,0,(sz[0])/2);
	dep[cen] = 0;
	return dfs1(cen,cen)*2;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 14964 KB Output is correct
2 Correct 77 ms 14568 KB Output is correct
3 Correct 86 ms 14836 KB Output is correct
4 Correct 80 ms 14768 KB Output is correct
5 Correct 78 ms 14788 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 10 ms 4968 KB Output is correct
3 Correct 15 ms 4992 KB Output is correct
4 Correct 16 ms 5092 KB Output is correct
5 Correct 22 ms 4972 KB Output is correct
6 Correct 18 ms 5124 KB Output is correct
7 Correct 17 ms 5008 KB Output is correct
8 Correct 17 ms 4956 KB Output is correct
9 Correct 18 ms 5212 KB Output is correct
10 Correct 19 ms 4956 KB Output is correct
11 Correct 13 ms 4956 KB Output is correct
12 Correct 22 ms 5064 KB Output is correct
13 Correct 16 ms 4956 KB Output is correct
14 Correct 25 ms 5100 KB Output is correct
15 Correct 24 ms 4952 KB Output is correct

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 14964 KB Output is correct
2 Correct 77 ms 14568 KB Output is correct
3 Correct 86 ms 14836 KB Output is correct
4 Correct 80 ms 14768 KB Output is correct
5 Correct 78 ms 14788 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 35 ms 5124 KB Output is correct
8 Correct 3348 ms 6872 KB Output is correct
9 Execution timed out 5540 ms 19760 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 14964 KB Output is correct
2 Correct 77 ms 14568 KB Output is correct
3 Correct 86 ms 14836 KB Output is correct
4 Correct 80 ms 14768 KB Output is correct
5 Correct 78 ms 14788 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 52 ms 5032 KB Output is correct
8 Execution timed out 5541 ms 7260 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 14964 KB Output is correct
2 Correct 77 ms 14568 KB Output is correct
3 Correct 86 ms 14836 KB Output is correct
4 Correct 80 ms 14768 KB Output is correct
5 Correct 78 ms 14788 KB Output is correct
6 Correct 3 ms 4956 KB Output is correct
7 Correct 10 ms 4968 KB Output is correct
8 Correct 15 ms 4992 KB Output is correct
9 Correct 16 ms 5092 KB Output is correct
10 Correct 22 ms 4972 KB Output is correct
11 Correct 18 ms 5124 KB Output is correct
12 Correct 17 ms 5008 KB Output is correct
13 Correct 17 ms 4956 KB Output is correct
14 Correct 18 ms 5212 KB Output is correct
15 Correct 19 ms 4956 KB Output is correct
16 Correct 13 ms 4956 KB Output is correct
17 Correct 22 ms 5064 KB Output is correct
18 Correct 16 ms 4956 KB Output is correct
19 Correct 25 ms 5100 KB Output is correct
20 Correct 24 ms 4952 KB Output is correct
21 Correct 2 ms 4956 KB Output is correct
22 Correct 35 ms 5124 KB Output is correct
23 Correct 3348 ms 6872 KB Output is correct
24 Execution timed out 5540 ms 19760 KB Time limit exceeded
25 Halted 0 ms 0 KB -