oj.uz

Submission #917094

# Submission time Handle Problem Language Result Execution time Memory
917094 2024-01-27T06:59:39 Z penguin133 Truck Driver (IOI23_deliveries) C++17
8 / 100
 5500 ms 25396 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[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[i] = x;
		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] += (ll)X - w[S];
		shit[tmp] += 1ll * (X - w[S]) * dist[S];
		if(!tmp)break;
		tmp = par[tmp];
	}
    */
	w[S] = X;
  dfs(0, 0);
	ll bruh = 0, ext = 0, cur = 0;
	while(1){
		ext += w[bruh];
		if(adj[bruh].empty()){
			cur += 2 * dist[bruh];
			break;
		}
		ll brr = 0, mx = 0;
		
		//ll x = bruh * 2 + 1, y = bruh * 2 + 2;
		for(auto [i, j] : adj[bruh])brr += tot[i], mx = max(mx, tot[i]);
		if(mx - ext > brr - mx){
			ll bruh2 = 0;
			for(auto [i, j] : adj[bruh])bruh2 += shit[i];
          int go = -1;
			for(auto [i, j] : adj[bruh]){
				if(tot[i] == mx){
					bruh2 -= shit[i];
					cur += (bruh2 - (brr - mx) * dist[bruh]) * 2;
					cur += j * 2 * (brr - mx + ext);
					ext += brr - mx;
                  assert(go == -1);
					go = i;
				}
			}
          assert(go != -1);
          bruh = go;
		}
		else{
			brr = 0; ll brr2 = 0;
			for(auto [i, j] : adj[bruh])brr += shit[i], brr2 += tot[i];
			cur += (brr - brr2 * 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 71 ms 14160 KB Output is correct
2 Correct 71 ms 13952 KB Output is correct
3 Correct 72 ms 14020 KB Output is correct
4 Correct 76 ms 13964 KB Output is correct
5 Correct 72 ms 14164 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 7 ms 6760 KB Output is correct
3 Correct 13 ms 6748 KB Output is correct
4 Correct 13 ms 6880 KB Output is correct
5 Correct 12 ms 6748 KB Output is correct
6 Correct 12 ms 6928 KB Output is correct
7 Correct 11 ms 6884 KB Output is correct
8 Correct 11 ms 6744 KB Output is correct
9 Correct 12 ms 6748 KB Output is correct
10 Correct 13 ms 6748 KB Output is correct
11 Correct 9 ms 6744 KB Output is correct
12 Correct 10 ms 6848 KB Output is correct
13 Correct 10 ms 6748 KB Output is correct
14 Incorrect 2 ms 6748 KB 3rd lines differ - on the 1st token, expected: '63174', found: '0'
15 Halted 0 ms 0 KB -

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 14160 KB Output is correct
2 Correct 71 ms 13952 KB Output is correct
3 Correct 72 ms 14020 KB Output is correct
4 Correct 76 ms 13964 KB Output is correct
5 Correct 72 ms 14164 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 25 ms 6876 KB Output is correct
8 Correct 1996 ms 8184 KB Output is correct
9 Execution timed out 5567 ms 16692 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 14160 KB Output is correct
2 Correct 71 ms 13952 KB Output is correct
3 Correct 72 ms 14020 KB Output is correct
4 Correct 76 ms 13964 KB Output is correct
5 Correct 72 ms 14164 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 34 ms 6744 KB Output is correct
8 Correct 3848 ms 9044 KB Output is correct
9 Execution timed out 5522 ms 25396 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 14160 KB Output is correct
2 Correct 71 ms 13952 KB Output is correct
3 Correct 72 ms 14020 KB Output is correct
4 Correct 76 ms 13964 KB Output is correct
5 Correct 72 ms 14164 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 7 ms 6760 KB Output is correct
8 Correct 13 ms 6748 KB Output is correct
9 Correct 13 ms 6880 KB Output is correct
10 Correct 12 ms 6748 KB Output is correct
11 Correct 12 ms 6928 KB Output is correct
12 Correct 11 ms 6884 KB Output is correct
13 Correct 11 ms 6744 KB Output is correct
14 Correct 12 ms 6748 KB Output is correct
15 Correct 13 ms 6748 KB Output is correct
16 Correct 9 ms 6744 KB Output is correct
17 Correct 10 ms 6848 KB Output is correct
18 Correct 10 ms 6748 KB Output is correct
19 Incorrect 2 ms 6748 KB 3rd lines differ - on the 1st token, expected: '63174', found: '0'
20 Halted 0 ms 0 KB -