oj.uz

Submission #916098

# Submission time Handle Problem Language Result Execution time Memory
916098 2024-01-25T09:34:14 Z emptypringlescan Truck Driver (IOI23_deliveries) C++17
29 / 100
 5500 ms 27524 KB 
#include <bits/stdc++.h>
using namespace std;
#include "deliveries.h"
vector<pair<int,long long> > adj[100005];
long long subsz[100005],arr[100005],ans;
void fsz(int x, int p){
	subsz[x]=arr[x];
	for(pair<int,long long> i:adj[x]){
		if(i.first==p) continue;
		fsz(i.first,x);
		subsz[x]+=subsz[i.first];
	}
}
void dfs(int x, int p){
	for(pair<int,long long> i:adj[x]){
		if(i.first==p) continue;
		ans+=i.second*min(subsz[i.first],1+subsz[0]-subsz[i.first]);
		dfs(i.first,x);
	}
}
void init(int n, vector<int> u, vector<int> v, vector<int> t, vector<int> w){
	for(int i=0; i<n-1; i++){
		adj[u[i]].push_back({v[i],t[i]});
		adj[v[i]].push_back({u[i],t[i]});
	}
	for(int i=0; i<n; i++){
		arr[i]=w[i];
	}
}
long long max_time(int s, int x){
	arr[s]=x;
	fsz(0,-1);
	ans=0;
	dfs(0,-1);
	return ans*2ll;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 14108 KB Output is correct
2 Correct 89 ms 13808 KB Output is correct
3 Correct 74 ms 14092 KB Output is correct
4 Correct 75 ms 14068 KB Output is correct
5 Correct 77 ms 14184 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4188 KB Output is correct
2 Correct 11 ms 4260 KB Output is correct
3 Correct 12 ms 4188 KB Output is correct
4 Correct 15 ms 4188 KB Output is correct
5 Correct 15 ms 4336 KB Output is correct
6 Correct 17 ms 4364 KB Output is correct
7 Correct 18 ms 4188 KB Output is correct
8 Correct 16 ms 4196 KB Output is correct
9 Correct 16 ms 4360 KB Output is correct
10 Correct 16 ms 4360 KB Output is correct
11 Correct 15 ms 4184 KB Output is correct
12 Correct 15 ms 4292 KB Output is correct
13 Correct 14 ms 4188 KB Output is correct
14 Correct 20 ms 4328 KB Output is correct
15 Correct 20 ms 4188 KB Output is correct

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 14108 KB Output is correct
2 Correct 89 ms 13808 KB Output is correct
3 Correct 74 ms 14092 KB Output is correct
4 Correct 75 ms 14068 KB Output is correct
5 Correct 77 ms 14184 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 31 ms 4344 KB Output is correct
8 Correct 3088 ms 6248 KB Output is correct
9 Execution timed out 5586 ms 20532 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 14108 KB Output is correct
2 Correct 89 ms 13808 KB Output is correct
3 Correct 74 ms 14092 KB Output is correct
4 Correct 75 ms 14068 KB Output is correct
5 Correct 77 ms 14184 KB Output is correct
6 Correct 2 ms 4188 KB Output is correct
7 Correct 43 ms 4188 KB Output is correct
8 Correct 4711 ms 6932 KB Output is correct
9 Execution timed out 5577 ms 27524 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 14108 KB Output is correct
2 Correct 89 ms 13808 KB Output is correct
3 Correct 74 ms 14092 KB Output is correct
4 Correct 75 ms 14068 KB Output is correct
5 Correct 77 ms 14184 KB Output is correct
6 Correct 3 ms 4188 KB Output is correct
7 Correct 11 ms 4260 KB Output is correct
8 Correct 12 ms 4188 KB Output is correct
9 Correct 15 ms 4188 KB Output is correct
10 Correct 15 ms 4336 KB Output is correct
11 Correct 17 ms 4364 KB Output is correct
12 Correct 18 ms 4188 KB Output is correct
13 Correct 16 ms 4196 KB Output is correct
14 Correct 16 ms 4360 KB Output is correct
15 Correct 16 ms 4360 KB Output is correct
16 Correct 15 ms 4184 KB Output is correct
17 Correct 15 ms 4292 KB Output is correct
18 Correct 14 ms 4188 KB Output is correct
19 Correct 20 ms 4328 KB Output is correct
20 Correct 20 ms 4188 KB Output is correct
21 Correct 2 ms 4188 KB Output is correct
22 Correct 31 ms 4344 KB Output is correct
23 Correct 3088 ms 6248 KB Output is correct
24 Execution timed out 5586 ms 20532 KB Time limit exceeded
25 Halted 0 ms 0 KB -