#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 / 2)ans2 = mid, hi = mid - 1;
else lo = mid + 1;
}
//ans is the midpoint
pi tmp = root->qry(ans + 1, n - 1), tmp2 = root->qry(0, ans - 1);
int cur = tmp.se - tmp2.se;
cur += 2 * ((sm / 2 - tmp.fi) * dist[ans] - (sm / 2 - tmp2.fi) * dist[ans]);
cur += 2 * dist[ans2];
return cur * 2;
}
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);
int cur = tmp.se - tmp2.se;
cur += 2 * ((sm / 2 - tmp.fi) * dist[ans] - (sm / 2 - tmp2.fi) * dist[ans]);
cur += 2 * dist[ans2];
return cur * 2;
}
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())
}
*/
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
94 ms |
28568 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '78098320' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
21336 KB |
3rd lines differ - on the 1st token, expected: '1627540', found: '2812216' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
94 ms |
28568 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '78098320' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
94 ms |
28568 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '78098320' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
94 ms |
28568 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '78098320' |
| 2 |
Halted |
0 ms |
0 KB |
- |
