Submission #1289233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289233		modwwe	Truck Driver (IOI23_deliveries)	C++20	100 / 100	603 ms	36424 KiB

deliveries

//#include "deliveries.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define ull unsigned long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "top1apio"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
using i128 = __int128;
int rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r)(rd);
}
void phongbeo();
const int inf = 1e17+7;
const int mod2 = 1e9+7;
//const ll base=67;
ll  n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2,
                                                               r2, center;
ll  i, s10, s12, k1, k2, k3, s11, lim, w, l, r, dem5, dem6, dem7, dem9, root, en;
ll el = 19;
struct ib
{
    ll a,b;
};
vector<ib> v[100001];
ll heavy[100001];
ll head[100001];
ll par[100001];
ll dist[100001];
ll in[100001],g[100001],ou[100001],num[100001];
ll dfs(ll x,ll y)
{
    ll sz=1,mxz=0;
    for(auto [f,cost]:v[x])
        if(f^y)
        {
            dist[f]=dist[x]+cost;
            par[f]=x;
            ll s=dfs(f,x);
            sz+=s;
            if(s>mxz)mxz=s,heavy[x]=f;
        }
    return sz;
}
void des(ll x,ll y)
{
    head[x]=y;
    in[x]=++dem;
    g[dem]=x;
    if(heavy[x]!=0)
    {
        des(heavy[x],y);
        for(auto [f,cost]:v[x])
            if(!in[f])
                des(f,f);
    }
    ou[x]=dem;
}
struct segtree
{
    ll t[400001],lazy[400001];
    void apply(ll node,ll x)
    {
        t[node]+=x;
        lazy[node]+=x;
    }
    void ff(ll x)
    {
        for(ll i=x*2; i<=x*2+1; i++)
            apply(i,lazy[x]);
        lazy[x]=0;
    }
    void upd(ll node,ll l,ll r,ll l1,ll r1,ll x)
    {
        if(l>r1||r<l1)return;
        if(l>=l1&&r<=r1)
        {
            apply(node,x);
            return;
        }
        ll mid=l+r>>1;
        if(lazy[node]!=0)ff(node);
        upd(node<<1,l,mid,l1,r1,x);
        upd(node<<1|1,mid+1,r,l1,r1,x);
        t[node]=max(t[node<<1],t[node<<1|1]);
    }
    ll get(ll node,ll l,ll r,ll x)
    {
        if(l==r)
        {
            return g[l];
        }
        if(lazy[node]!=0)ff(node);
        ll mid=l+r>>1;
        if(t[node<<1|1]*2>=x)return get(node<<1|1,mid+1,r,x);
        return get(node<<1,l,mid,x);
    }
} st;
struct fenwicktree
{
    ll bit[100001];
    void upd(ll x,ll y)
    {
        for(x; x<=n; x+=x&-x)
            bit[x]+=y;
    }
    ll get(ll x)
    {
        ll s=0;
        for(x; x; x-=x&-x)
            s+=bit[x];
        return s;
    }
} fen,fen2,fen3;
void buff(ll x,ll y,ll z)
{
    fen.upd(in[x],y*z-dist[x]*z*2);
    st.upd(1,1,n,in[head[x]],in[x],z);
    if(head[x]!=0)buff(par[head[x]],y,z);
}
void init(int N,vector<int> U,vector<int> V,vector<int> T,vector<int> W)
{
    n=N;
    for(int i=0; i<n-1; i++)
        v[U[i]].pb({V[i],T[i]}),
        v[V[i]].pb({U[i],T[i]});
    for(int i=0; i<n; i++)
        num[i]=W[i];
    num[0]++;
    dfs(0,-1);
    des(0,0);
    for(int i=0; i<n; i++)
        if(num[i]!=0)
        {
            buff(i,dist[i],num[i]);
            fen2.upd(in[i],num[i]*dist[i]);
            fen3.upd(in[i],num[i]);
        }
}
ll gg(ll x,ll y,ll z)
{
    return fen2.get(y)-fen2.get(x)-(fen3.get(y)-fen3.get(x))*z*2;
}
ll hihi(ll x,ll y)
{
    return fen.get(x)-fen.get(y);
}
ll max_time(int x,int y)
{
    if(x==0)y++;
    buff(x,dist[x],y-num[x]);
    fen2.upd(in[x],(y-num[x])*dist[x]);
    fen3.upd(in[x],y-num[x]);
    num[x]=y;
    ll center=st.get(1,1,n,st.t[1]);
    s4=dist[center]*st.t[1];
    ll lastl=0,lastr=0;
    while(true)
    {
        s4+=gg(in[center]-1,ou[center],dist[center])-gg(lastl,lastr,dist[center]);
        if(center!=head[center])s4+=hihi(in[par[center]],in[head[center]]-1);
        center=head[center];
        lastl=in[center]-1;
        lastr=ou[center];
        if(center==0)break;
        center=par[center];
    }
    return s4*2;
}

Compilation message (stderr)

deliveries.cpp:28:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   28 | const int inf = 1e17+7;
      |                 ~~~~^~

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