oj.uz

Submission #856936

# Submission time Handle Problem Language Result Execution time Memory
856936 2023-10-04T23:18:11 Z Edu175 Truck Driver (IOI23_deliveries) C++17
29 / 100
 5500 ms 23088 KB 
#include "deliveries.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto asd:v)cout<<asd<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=1e5+5;

ll n;
vector<ii>g[MAXN];
ll tot=1; //extra zero (return)

ll t[MAXN],c[MAXN];
ll res=0;

void dfs(ll x, ll f){
	c[x]=t[x];
	for(auto [y,w]:g[x])if(y!=f){
		dfs(y,x);
		res+=2*w*min(c[y],tot-c[y]);
		c[x]+=c[y];
	}
}

void init(int N, std::vector<int> u, std::vector<int> v, std::vector<int> w, std::vector<int> T) {
	n=N;
	fore(i,0,SZ(u)){
		g[u[i]].pb({v[i],w[i]});
		g[v[i]].pb({u[i],w[i]});
	}
	fore(i,0,n)t[i]=T[i],tot+=t[i];
}

long long max_time(int s, int x) {
	tot+=-t[s]+x;
	t[s]=x;
	res=0;
	dfs(0,-1);
	return res;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 11408 KB Output is correct
2 Correct 69 ms 11348 KB Output is correct
3 Correct 72 ms 11432 KB Output is correct
4 Correct 70 ms 11392 KB Output is correct
5 Correct 70 ms 11604 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 6 ms 4188 KB Output is correct
3 Correct 7 ms 4188 KB Output is correct
4 Correct 9 ms 4188 KB Output is correct
5 Correct 9 ms 4188 KB Output is correct
6 Correct 9 ms 4188 KB Output is correct
7 Correct 9 ms 4300 KB Output is correct
8 Correct 9 ms 4188 KB Output is correct
9 Correct 9 ms 4188 KB Output is correct
10 Correct 9 ms 4348 KB Output is correct
11 Correct 7 ms 4184 KB Output is correct
12 Correct 10 ms 4188 KB Output is correct
13 Correct 9 ms 4188 KB Output is correct
14 Correct 12 ms 4312 KB Output is correct
15 Correct 11 ms 4388 KB Output is correct

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 11408 KB Output is correct
2 Correct 69 ms 11348 KB Output is correct
3 Correct 72 ms 11432 KB Output is correct
4 Correct 70 ms 11392 KB Output is correct
5 Correct 70 ms 11604 KB Output is correct
6 Correct 1 ms 4188 KB Output is correct
7 Correct 19 ms 4188 KB Output is correct
8 Correct 1833 ms 5820 KB Output is correct
9 Execution timed out 5507 ms 15940 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 11408 KB Output is correct
2 Correct 69 ms 11348 KB Output is correct
3 Correct 72 ms 11432 KB Output is correct
4 Correct 70 ms 11392 KB Output is correct
5 Correct 70 ms 11604 KB Output is correct
6 Correct 2 ms 4184 KB Output is correct
7 Correct 23 ms 4376 KB Output is correct
8 Correct 2704 ms 6524 KB Output is correct
9 Execution timed out 5538 ms 23088 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 11408 KB Output is correct
2 Correct 69 ms 11348 KB Output is correct
3 Correct 72 ms 11432 KB Output is correct
4 Correct 70 ms 11392 KB Output is correct
5 Correct 70 ms 11604 KB Output is correct
6 Correct 3 ms 4188 KB Output is correct
7 Correct 6 ms 4188 KB Output is correct
8 Correct 7 ms 4188 KB Output is correct
9 Correct 9 ms 4188 KB Output is correct
10 Correct 9 ms 4188 KB Output is correct
11 Correct 9 ms 4188 KB Output is correct
12 Correct 9 ms 4300 KB Output is correct
13 Correct 9 ms 4188 KB Output is correct
14 Correct 9 ms 4188 KB Output is correct
15 Correct 9 ms 4348 KB Output is correct
16 Correct 7 ms 4184 KB Output is correct
17 Correct 10 ms 4188 KB Output is correct
18 Correct 9 ms 4188 KB Output is correct
19 Correct 12 ms 4312 KB Output is correct
20 Correct 11 ms 4388 KB Output is correct
21 Correct 1 ms 4188 KB Output is correct
22 Correct 19 ms 4188 KB Output is correct
23 Correct 1833 ms 5820 KB Output is correct
24 Execution timed out 5507 ms 15940 KB Time limit exceeded
25 Halted 0 ms 0 KB -