oj.uz

Submission #883114

# Submission time Handle Problem Language Result Execution time Memory
883114 2023-12-04T14:49:05 Z amunduzbaev Truck Driver (IOI23_deliveries) C++17
29 / 100
 1087 ms 49740 KB 
#include "deliveries.h"
 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;
//~ #define int ll
 
const int N = 1e5 + 5;
int n, cur;
ll tot;
vector<vector<ar<int, 2>>> edges;
vector<int> w;
vector<ar<int, 2>> par;
vector<ll> sub;
 
struct ST{
	ll Max[N << 2], sum[N << 2], f[N << 2], b[N << 2];
	
	void set(int i, int v, int lx, int rx, int x){
		if(lx == rx) { 
			b[x] = v; return;
		}
		
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		
		b[x] = b[x << 1] + b[x << 1 | 1];
	} void set(int i, int v) { set(i, v, 0, N, 1); }
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		Max[x << 1] += f[x], Max[x << 1 | 1] += f[x];
		sum[x << 1] += b[x << 1] * f[x];
		sum[x << 1 | 1] += b[x << 1 | 1] * f[x];
		f[x << 1] += f[x], f[x << 1 | 1] += f[x];
		
		f[x] = 0;
	}
	
	void add(int l, int r, int v, int lx, int rx, int x){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			Max[x] += v;
			sum[x] += b[x] * v;
			f[x] += v;
			return;
		}
		
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		add(l, r, v, lx, m, x << 1);
		add(l, r, v, m + 1, rx, x << 1 | 1);
		
		Max[x] = max(Max[x << 1], Max[x << 1 | 1]);
		sum[x] = sum[x << 1] + sum[x << 1 | 1];
	} void add(int l, int r, int v) { add(l, r, v, 0, N, 1); }
	
	ll get(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l) return 0ll;
		if(lx >= l && rx <= r) return sum[x];
		
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		
		return get(l, r, lx, m, x << 1) + get(l, r, m + 1, rx, x << 1 | 1);
	} ll get(int l, int r) { return get(l, r, 0, N, 1) ; }
	
	ll get_(int l, int r, int lx, int rx, int x){
		if(lx > r || rx < l ) return 0ll;
		if(lx >= l && rx <= r) return Max[x];
		
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		
		return max(get_(l, r, lx, m, x << 1), get_(l, r, m + 1, rx, x << 1 | 1));
	} ll get_(int l, int r) { return get_(l, r, 0, N, 1); }
	
	int big(int v, int lx, int rx, int x){
		if(lx == rx) return lx;
		
		int m = (lx + rx) >> 1;
		push(x, lx, rx);
		
		if(Max[x << 1 | 1] >= v) return big(v, m + 1, rx, x << 1 | 1);
		else return big(v, lx, m, x << 1);
	}
	
	int big(int v) { return big(v, 0, N, 1); }
}tree;
 
vector<int> cnt, hev, head, pos, ver;
vector<ll> pref;
 
void init(int N, vector<int> u, vector<int> v, vector<int> t, vector<int> W) {
	w = W; n = N;
	edges.resize(n);
	sub.resize(n);
	par.resize(n);
	cnt.resize(n), hev.resize(n);
	head.resize(n), pos.resize(n), ver.resize(n);
	pref.resize(n);
	
	tot = 2;
	for(int i=0;i<n;i++) tot += w[i];
	
	for(int i=0;i + 1<n;i++){
		edges[u[i]].push_back({v[i], 2 * t[i]});
		edges[v[i]].push_back({u[i], 2 * t[i]});
	}
	
	function<void(int, int)> dfs = [&](int u, int p){
		sub[u] = w[u] + (u == 0) * 2;
		cnt[u] = 1, hev[u] = -1;
		
		for(auto [x, c] : edges[u]){
			if(x == p) continue;
			par[x] = {u, c};
			pref[x] = pref[u] + c;
			
			dfs(x, u);
			if(hev[u] == -1 || cnt[x] > cnt[hev[u]]) hev[u] = x;
			
			cnt[u] += cnt[x];
			sub[u] += sub[x];
		}
	};
	
	dfs(0, 0);
	
	int last = 0;
	function<void(int, int, int)> dec = [&](int u, int p, int P){
		pos[u] = last++, ver[pos[u]] = u, head[u] = P;
		if(~hev[u]){
			dec(hev[u], u, P);
		}
		
		for(auto [x, c] : edges[u]){
			if(x == p || x == hev[u]) continue;
			dec(x, u, x);
		}
	};
	
	dec(0, 0, 0);
	for(int i=0;i<n;i++){
		tree.set(pos[i], par[i][1]);
	}
	for(int i=0;i<n;i++){
		tree.add(pos[i], pos[i], sub[i]);
	}
	
	//~ for(int i=0;i<n;i++){
		//~ cout<<sub[i]<<" ";
	//~ } cout<<endl;
	//~ for(int i=0;i<n;i++){
		//~ cout<<par[i][1]<<" ";
	//~ } cout<<endl;
	//~ for(int i=0;i<n;i++){
		//~ cout<<tree.get(pos[i], pos[i])<<" ";
	//~ } cout<<endl;
	//~ for(int i=0;i<n;i++){
		//~ cout<<tree.get_(pos[i], pos[i])<<" ";
	//~ }
	//~ cout<<endl;
}
 
ll get(int u){
	ll res = 0;
	while(head[u]){
		res += tree.get(pos[head[u]], pos[u]);
		u = par[head[u]][0];
	}
	
	res += tree.get(pos[head[u]], pos[u]);
	return res;
}
 
void add(int u, int x){
	while(head[u]){
		tree.add(pos[head[u]], pos[u], x);
		u = par[head[u]][0];
	}
	
	tree.add(pos[head[u]], pos[u], x);
}
 
ll max_time(int s, int x) {
	x = -w[s] + x;
	tot += x;
	w[s] += x;
	
	add(s, x);
	
	//~ cout<<tot<<" "<<(tot + 1) / 2<<"\n";
	//~ for(int i=0;i<n;i++){
		//~ cout<<tree.get_(i, i)<<" ";
	//~ } cout<<"\n";
	
	//~ cout<<tree.Max[1]<<endl;
	//~ cout<<(tot + 1) / 2<<endl;
	//~ cout<<tree.big((tot + 1) / 2)<<endl;;
	
	int cen = ver[tree.big((tot + 1) / 2)];
	
	//~ cout<<cen<<" "<<tree.sum[1]<<" "<<(tot - 1) * pref[cen]<<" "<<get(cen)<<"\n";
	
	ll res = tree.sum[1] + (tot - 1) * pref[cen];
	res -= get(cen) * 2;
	
	return res;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 20864 KB Output is correct
2 Correct 195 ms 20312 KB Output is correct
3 Correct 166 ms 20660 KB Output is correct
4 Correct 166 ms 20556 KB Output is correct
5 Correct 177 ms 20572 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10784 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 2 ms 10952 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 4 ms 10952 KB Output is correct
6 Correct 3 ms 10840 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 3 ms 10844 KB Output is correct
11 Correct 4 ms 10844 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 3 ms 10844 KB Output is correct
14 Correct 3 ms 10948 KB Output is correct
15 Correct 3 ms 10840 KB Output is correct

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 20864 KB Output is correct
2 Correct 195 ms 20312 KB Output is correct
3 Correct 166 ms 20660 KB Output is correct
4 Correct 166 ms 20556 KB Output is correct
5 Correct 177 ms 20572 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 7 ms 10844 KB Output is correct
8 Correct 75 ms 13324 KB Output is correct
9 Correct 1085 ms 36948 KB Output is correct
10 Correct 1087 ms 36916 KB Output is correct
11 Correct 1046 ms 36852 KB Output is correct
12 Incorrect 767 ms 39284 KB 3rd lines differ - on the 1st token, expected: '68896721505042', found: '53986571112838'
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 20864 KB Output is correct
2 Correct 195 ms 20312 KB Output is correct
3 Correct 166 ms 20660 KB Output is correct
4 Correct 166 ms 20556 KB Output is correct
5 Correct 177 ms 20572 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 4 ms 11100 KB Output is correct
8 Correct 28 ms 14420 KB Output is correct
9 Correct 302 ms 47628 KB Output is correct
10 Correct 301 ms 47640 KB Output is correct
11 Correct 284 ms 47668 KB Output is correct
12 Incorrect 279 ms 49740 KB 3rd lines differ - on the 1st token, expected: '125599030041442104', found: '334945339228128'
13 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 20864 KB Output is correct
2 Correct 195 ms 20312 KB Output is correct
3 Correct 166 ms 20660 KB Output is correct
4 Correct 166 ms 20556 KB Output is correct
5 Correct 177 ms 20572 KB Output is correct
6 Correct 2 ms 10784 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 2 ms 10952 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 4 ms 10952 KB Output is correct
11 Correct 3 ms 10840 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 3 ms 10844 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 3 ms 10844 KB Output is correct
16 Correct 4 ms 10844 KB Output is correct
17 Correct 3 ms 10844 KB Output is correct
18 Correct 3 ms 10844 KB Output is correct
19 Correct 3 ms 10948 KB Output is correct
20 Correct 3 ms 10840 KB Output is correct
21 Correct 2 ms 10588 KB Output is correct
22 Correct 7 ms 10844 KB Output is correct
23 Correct 75 ms 13324 KB Output is correct
24 Correct 1085 ms 36948 KB Output is correct
25 Correct 1087 ms 36916 KB Output is correct
26 Correct 1046 ms 36852 KB Output is correct
27 Incorrect 767 ms 39284 KB 3rd lines differ - on the 1st token, expected: '68896721505042', found: '53986571112838'
28 Halted 0 ms 0 KB -