oj.uz

Submission #917084

# Submission time Handle Problem Language Result Execution time Memory
917084 2024-01-27T06:32:25 Z penguin133 Truck Driver (IOI23_deliveries) C++17
22 / 100
 174 ms 41672 KB 
#include <bits/stdc++.h>
using namespace std;
 
#include "deliveries.h"
//#define int long long
typedef long long ll;
#define pi pair<ll, ll>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
vector <int> t, w, u, v;
ll dist[300005];
 
struct node{
	int s, e, m; ll val, val2;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
		val = val2 = 0;
	}
	
	void upd(int p, ll v){
		if(s == e){
			val = v;
			val2 = v * dist[p];
			return;
		}
		if(p <= m)l->upd(p, v);
		else r->upd(p, v);
		val = l->val + r->val;
		val2 = l->val2 + r->val2;
	}
	
	pi qry(int a, int b){
		if(a > b)return {0, 0};
		if(s == a && b == e)return {val,val2};
		if(b <= m)return l->qry(a, b);
		if(a > m)return r->qry(a ,b);
		pi lft = l->qry(a, m), rgt = r->qry(m+1, b);
		return {lft.fi + rgt.fi, lft.se + rgt.se};
	}
}*root;
ll n, sm, par[20][100005], shit[100005], tot[100005], cnt = 0;
vector <pi> adj[100005];
void dfs(int x, ll cur){
	dist[x] = cur;
	tot[x] = w[x], shit[x] = dist[x] * w[x];
	for(auto [i, j] : adj[x]){
		par[0][i] = x;
		for(int k = 1; k <= 19; k++)par[k][i] = par[k-1][par[k-1][i]];
		dfs(i, cur + j);
		tot[x] += tot[i];
		shit[x] += shit[i];
	}
}
/*
int lca(int u, int v){
	if(dep[u] > dep[v])swap(u, v);
	int df = dep[v] - dep[u];
	for(int i = 0; i <= 19; i++)if(df >> i & 1)v = par[i][v];
	if(u == v)return u;
	for(int i = 19; i >= 0; i--)if(par[i][u] != par[i][v])u = par[i][u], v = par[i][v];
	return par[0][u];
}
*/
 
void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
	u = U; v = V; t = T; w = W;
	for(int i = 0; i < N - 1; i++)adj[U[i]].push_back({V[i], T[i]});
	dfs(0, 0);
	//for(int i = 0; i < N; i++)back[S[i]] = i;
	//for(int i = 1; i < N; i++)dist[i] = dist[i - 1] + t[i - 1];
	//root = new node(0, N - 1);
	n = N;
	//for(int i = 0; i < N; i++)root->upd(i, w[i]), sm += w[i];
	return;
}
 
long long max_time(int S, int X) {
	
	int tmp = S;
	while(1){
		tot[tmp] += X - w[S];
		shit[tmp] += (X - w[S]) * dist[S];
		if(!tmp)break;
		tmp = (tmp - 1) / 2;
	}
	w[S] = X;
	ll bruh = 0, ext = 0, cur = 0;
	while(1){
		ext += w[bruh];
		if(adj[bruh].empty()){
			cur += 2 * dist[bruh];
			break;
		}
		ll x = bruh * 2 + 1, y = bruh * 2 + 2;
		ll mx = max(tot[x], tot[y]), mn = min(tot[x], tot[y]);
		if(mx - ext <= mn){
			cur += ((shit[x] + shit[y]) - (tot[x] + tot[y]) * dist[bruh]) * 2 + 2 * dist[bruh];
			break;
		}
		if(tot[x] > tot[y]){
			cur += (shit[y] - tot[y] * dist[bruh]) * 2;
			cur += adj[bruh][0].se * 2 * (tot[y] + ext);
			ext += tot[y];
			bruh = x;
		}
		else{
			cur += (shit[x] - tot[x] * dist[bruh]) * 2;
			cur += adj[bruh][1].se * 2 * (tot[x] + ext);
			ext += tot[x];
			bruh = y;
		}
	}
	return cur;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 28496 KB Output is correct
2 Correct 70 ms 28304 KB Output is correct
3 Correct 80 ms 28496 KB Output is correct
4 Correct 75 ms 28240 KB Output is correct
5 Correct 71 ms 28496 KB Output is correct

Subtask #2
0.0 / 21.0

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

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 28496 KB Output is correct
2 Correct 70 ms 28304 KB Output is correct
3 Correct 80 ms 28496 KB Output is correct
4 Correct 75 ms 28240 KB Output is correct
5 Correct 71 ms 28496 KB Output is correct
6 Correct 5 ms 21084 KB Output is correct
7 Correct 6 ms 21084 KB Output is correct
8 Correct 18 ms 22876 KB Output is correct
9 Correct 154 ms 38916 KB Output is correct
10 Correct 174 ms 38964 KB Output is correct
11 Correct 150 ms 39012 KB Output is correct
12 Correct 123 ms 41524 KB Output is correct
13 Correct 123 ms 41496 KB Output is correct
14 Correct 131 ms 41672 KB Output is correct

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 28496 KB Output is correct
2 Correct 70 ms 28304 KB Output is correct
3 Correct 80 ms 28496 KB Output is correct
4 Correct 75 ms 28240 KB Output is correct
5 Correct 71 ms 28496 KB Output is correct
6 Incorrect 4 ms 21080 KB 3rd lines differ - on the 1st token, expected: '129238', found: '885098'
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 28496 KB Output is correct
2 Correct 70 ms 28304 KB Output is correct
3 Correct 80 ms 28496 KB Output is correct
4 Correct 75 ms 28240 KB Output is correct
5 Correct 71 ms 28496 KB Output is correct
6 Incorrect 4 ms 21108 KB 3rd lines differ - on the 1st token, expected: '1627540', found: '9045838'
7 Halted 0 ms 0 KB -