oj.uz

Submission #917076

# Submission time Handle Problem Language Result Execution time Memory
917076 2024-01-27T06:05:15 Z penguin133 Truck Driver (IOI23_deliveries) C++17
29 / 100
 1039 ms 60832 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;
	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);
	}
}
/*
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) {
	
	root->upd(S, X);
	sm += X - w[S];
	w[S] = X;
	if(sm%2){
		int lo = 0, hi = n - 1, ans = -1;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			if(root->qry(mid, n - 1).fi >= (sm + 1) / 2)ans = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		lo = 0, hi = n - 1; int ans2 = hi + 1;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			if(root->qry(0, mid).fi >= (sm + 1) / 2)ans2 = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		//ans is the midpoint
		//cout << ans << ' ' << ans2 << '\n';
		pi tmp = root->qry(ans + 1, n - 1), tmp2 = root->qry(0, ans - 1);
		ll cur = 2 * (tmp.se - tmp2.se);
		cur += 2 * ((sm / 2 - tmp.fi) * dist[ans] - (sm / 2 - tmp2.fi) * dist[ans]);
		cur += 2 * dist[ans2];
		return cur;
	}
	else{
		int lo = 0, hi = n - 1, ans = -1;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			if(root->qry(mid, n - 1).fi >= (sm + 1) / 2)ans = mid, lo = mid + 1;
			else hi = mid - 1;
		}
		lo = 0, hi = n - 1; int ans2 = hi + 1;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			if(root->qry(0, mid).fi >= sm / 2)ans2 = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		//cout << ans << ' ' << ans2 << '\n';
		//ans is the midpoint
		pi tmp = root->qry(ans + 1, n - 1), tmp2 = root->qry(0, ans - 1);
		ll cur = 2 * (tmp.se - tmp2.se);
		cur += 2 * ((sm / 2 - tmp.fi) * dist[ans] - (sm / 2 - tmp2.fi) * dist[ans]);
		cur += 2 * dist[ans2];
		return cur;
	}
	return 0;
	
	/*
	int tmp = S;
	do{
		tot[tmp] += X - w[S];
		sm[tmp] += (X - w[S]) * dist[S];
		tmp /= 2;
	}while(tmp);
	int bruh = 0, ext = 0, cur = 0;
	while(1){
		if(adj[bruh].empty())
	}
	*/
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 28496 KB Output is correct
2 Correct 78 ms 28128 KB Output is correct
3 Correct 77 ms 28496 KB Output is correct
4 Correct 77 ms 28244 KB Output is correct
5 Correct 77 ms 28304 KB Output is correct

Subtask #2
0.0 / 21.0

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

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 28496 KB Output is correct
2 Correct 78 ms 28128 KB Output is correct
3 Correct 77 ms 28496 KB Output is correct
4 Correct 77 ms 28244 KB Output is correct
5 Correct 77 ms 28304 KB Output is correct
6 Incorrect 5 ms 21084 KB 3rd lines differ - on the 1st token, expected: '45306', found: '8134'
7 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 28496 KB Output is correct
2 Correct 78 ms 28128 KB Output is correct
3 Correct 77 ms 28496 KB Output is correct
4 Correct 77 ms 28244 KB Output is correct
5 Correct 77 ms 28304 KB Output is correct
6 Correct 4 ms 21080 KB Output is correct
7 Correct 8 ms 21416 KB Output is correct
8 Correct 72 ms 24332 KB Output is correct
9 Correct 1039 ms 57672 KB Output is correct
10 Correct 999 ms 57532 KB Output is correct
11 Correct 1020 ms 57648 KB Output is correct
12 Correct 742 ms 60832 KB Output is correct
13 Correct 712 ms 60780 KB Output is correct
14 Correct 727 ms 57076 KB Output is correct

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 28496 KB Output is correct
2 Correct 78 ms 28128 KB Output is correct
3 Correct 77 ms 28496 KB Output is correct
4 Correct 77 ms 28244 KB Output is correct
5 Correct 77 ms 28304 KB Output is correct
6 Incorrect 4 ms 21084 KB 3rd lines differ - on the 1st token, expected: '1627540', found: '820336'
7 Halted 0 ms 0 KB -