#include "deliveries.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
vector<pair<ll,ll>>V[LIM];
ll trma[4*LIM], trsum[4*LIM], trwag[4*LIM], lazy[4*LIM], N=1, n;
ll odl[LIM], jaki[LIM], kto[LIM], ile[LIM], oc[LIM], sci[LIM], W[LIM], akt, aktans, aktile;
void DFS(int x, int o) {
ile[x]=1;
for(auto i : V[x]) if(i.st!=o) {
odl[i.st]=odl[x]+i.nd;
DFS(i.st, x);
ile[x]+=ile[i.st];
}
rep(i, V[x].size()) if(V[x][0].st==o || (V[x][i].st!=o && ile[V[x][0].st]<ile[V[x][i].st])) swap(V[x][i], V[x][0]);
}
void DFS2(int x, int o) {
jaki[x]=akt;
kto[akt]=x;
++akt;
oc[x]=o;
for(auto i : V[x]) if(i.st==o) trwag[N+akt-1]=i.nd;
if(V[x].size()==1) return;
sci[V[x][0].st]=sci[x];
DFS2(V[x][0].st, x);
for(auto i : V[x]) if(i.st!=V[x][0].st && i.st!=o) DFS2(i.st, x);
}
void spl(int v) {
trma[2*v]+=lazy[v];
trma[2*v+1]+=lazy[v];
trsum[2*v]+=lazy[v]*trwag[2*v];
trsum[2*v+1]+=lazy[v]*trwag[2*v+1];
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b, ll x) {
if(r<a || b<l) return;
if(a<=l && r<=b) {
trma[v]+=x;
trsum[v]+=trwag[v]*x;
lazy[v]+=x;
return;
}
if(lazy[v]) spl(v);
int mid=(l+r)/2;
upd(2*v, l, mid, a, b, x);
upd(2*v+1, mid+1, r, a, b, x);
trma[v]=max(trma[2*v], trma[2*v+1]);
trsum[v]=trsum[2*v]+trsum[2*v+1];
}
ll cnt(int v, int l, int r, int a, int b) {
if(r<a || b<l) return 0;
if(a<=l && r<=b) return trsum[v];
if(lazy[v]) spl(v);
int mid=(l+r)/2;
return cnt(2*v, l, mid, a, b)+cnt(2*v+1, mid+1, r, a, b);
}
void zmiana(int v, ll x) {
W[v]+=x;
aktile+=x;
aktans+=odl[v]*x;
while(sci[v]!=0) {
upd(1, 0, N-1, jaki[sci[v]], jaki[v], x);
v=oc[sci[v]];
}
upd(1, 0, N-1, jaki[sci[v]], jaki[v], x);
}
ll licz(int v) {
ll ans=0;
while(sci[v]!=0) {
ans+=cnt(1, 0, N-1, jaki[sci[v]], jaki[v]);
v=oc[sci[v]];
}
ans+=cnt(1, 0, N-1, jaki[sci[v]], jaki[v]);
return ans;
}
void init(int _N, vector<int>_U, vector<int>_V, vector<int>_T, vector<int>_W) {
n=_N;
while(N<n) N*=2;
rep(i, n-1) {
V[_U[i]].pb({_V[i], _T[i]});
V[_V[i]].pb({_U[i], _T[i]});
}
rep(i, n) sci[i]=i;
DFS(0, 0);
DFS2(0, 0);
for(int i=N-1; i; --i) trwag[i]=trwag[2*i]+trwag[2*i+1];
++_W[0];
rep(i, n) zmiana(i, _W[i]);
}
ll max_time(int S, int X) {
if(!S) ++X;
zmiana(S, X-W[S]);
ll v=1;
while(v<N) {
if(lazy[v]) spl(v);
v=2*v+1;
if(trma[v]<=aktile/2) --v;
}
v-=N;
v=kto[v];
return 2*(aktans+aktile*odl[v]-2*licz(v));
}
Compilation message
deliveries.cpp: In function 'void DFS(int, int)':
deliveries.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
| ^
deliveries.cpp:21:3: note: in expansion of macro 'rep'
21 | rep(i, V[x].size()) if(V[x][0].st==o || (V[x][i].st!=o && ile[V[x][0].st]<ile[V[x][i].st])) swap(V[x][i], V[x][0]);
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
24404 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '122820310' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
16472 KB |
Output is correct |
| 2 |
Correct |
4 ms |
16472 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
14424 KB |
3rd lines differ - on the 1st token, expected: '26303740', found: '95320192' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
24404 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '122820310' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
24404 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '122820310' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
79 ms |
24404 KB |
3rd lines differ - on the 1st token, expected: '39049160', found: '122820310' |
| 2 |
Halted |
0 ms |
0 KB |
- |
