Submission #939783

#	Time	Username	Problem	Language	Result	Execution time	Memory
939783		AdamGS	Truck Driver (IOI23_deliveries)	C++17	100 / 100	885 ms	48688 KiB

deliveries

#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 && V[x][0].st==o) 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 (stderr)

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]);
      |   ^~~

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 36 / 36