#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;
do{
tot[tmp] += X - w[S];
shit[tmp] += (X - w[S]) * dist[S];
tmp = (tmp - 1) / 2;
}while(tmp);
w[S] = X;
int bruh = 0, ext = 0, cur = 0;
while(1){
ext += w[bruh];
if(adj[bruh].empty()){
cur += 2 * dist[bruh];
break;
}
int 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;
break;
}
if(tot[x] > tot[y]){
cur += (shit[y] - tot[y] * dist[bruh]) * 2;
cur += adj[bruh][0].se * 2 * shit[y];
ext = tot[x] - ext - tot[y];
bruh = x;
}
else{
cur += (shit[x] - tot[x] * dist[bruh]) * 2;
cur += adj[bruh][1].se * 2 * shit[x];
ext = tot[y] - ext - tot[x];
bruh = y;
}
}
return cur;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
68 ms |
27728 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '146' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
21084 KB |
3rd lines differ - on the 1st token, expected: '1627540', found: '60442214' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
68 ms |
27728 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '146' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
68 ms |
27728 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '146' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
68 ms |
27728 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '146' |
| 2 |
Halted |
0 ms |
0 KB |
- |
