oj.uz

Submission #856947

# Submission time Handle Problem Language Result Execution time Memory
856947 2023-10-05T00:05:42 Z Edu175 Truck Driver (IOI23_deliveries) C++17
100 / 100
 2480 ms 44508 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,oia=b;i<oia;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define imp(v) for(auto asd:v)cout<<asd<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=1e5+5;

vector<ii> g[MAXN];
ll sw[MAXN],w[MAXN],fa[MAXN],sz[MAXN]; //init w0=0,f0=-1

void dfs(ll x){
    sz[x]=1;
    sw[x]=w[x];
    if(fa[x]!=-1)sw[x]+=sw[fa[x]];
    for(auto [y,p]:g[x])if(y!=fa[x]){
        w[y]=p;
        fa[y]=x;
        dfs(y);
        sz[x]+=sz[y];
    }
}
ll pos[MAXN],ipos[MAXN],head[MAXN],qidx=0;

void dfs2(ll x, ll f=-1){
    if(f==-1)f=x;
    head[x]=f;
    pos[x]=qidx,ipos[qidx]=x; qidx++;
    ll mx=-1;
    for(auto [y,sus]:g[x])if(y!=fa[x]){
            if(mx==-1||sz[y]>sz[mx])mx=y;
    }
    if(mx==-1)return;
    dfs2(mx,f);
    for(auto [y,sus]:g[x])if(y!=fa[x]&&y!=mx)dfs2(y);
}
void hld_init(){
	w[0]=0; fa[0]=-1;
	dfs(0); dfs2(0);
}
ll oper(ll a, ll b, ll t){
    if(t)return max(a,b);
    return a+b;
}

ll calc(ll s, ll e, ll a, ll v, ll t){ //need pos y ipos
    if(t)return a+v;
    ll x=ipos[s],y=ipos[e-1];
    ll sum=sw[y];
    if(x)sum-=sw[fa[x]];
    return a+sum*v;
} 

struct STree{
    ll n,t; vector<ll>st, lazy;
    STree(ll n, ll t):n(n),t(t),st(4*n+5),lazy(4*n+5){}
    STree(){}
    void push(ll k, ll s, ll e){
        st[k]=calc(s,e,st[k],lazy[k],t);
        //cout<<"push "<<k<<","<<s<<" "<<e<<endl;
        if(s+1!=e){
            lazy[2*k]+=lazy[k];
            lazy[2*k+1]+=lazy[k];
        }
        lazy[k]=0;
    }
    void upd(ll k, ll s, ll e, ll a, ll b, ll v){
        push(k,s,e);
        if(e<=a||b<=s)return;
        if(a<=s&&e<=b){
            lazy[k]+=v;
            push(k,s,e);
            return;
        }
        ll m=(s+e)/2;
        upd(2*k  ,s,m,a,b,v);
        upd(2*k+1,m,e,a,b,v);
        st[k]=oper(st[2*k],st[2*k+1],t);
    }
    ll query(ll k, ll s, ll e, ll a, ll b){
        push(k,s,e);
        if(e<=a||b<=s)return 0;
        if(a<=s&&e<=b)return st[k];
        ll m=(s+e)/2;
        return oper(query(2*k,s,m,a,b),query(2*k+1,m,e,a,b),t);
    }
    //find
    ll find(ll k, ll s, ll e, ll x){
    	push(k,s,e);
    	if(s+1==e)return ipos[s];
    	//cout<<"find "<<k<<" "<<s<<","<<e<<" "<<x<<endl;
    	ll m=(s+e)/2;
    	push(2*k,s,m); push(2*k+1,m,e);
    	if(st[2*k+1]>x){return find(2*k+1,m,e,x);}
    	return find(2*k,s,m,x);
    }
    void upd(ll a, ll b, ll v){upd(1,0,n,a,b,v);}
    ll query(ll a, ll b){return query(1,0,n,a,b);}
    ll find(ll x){assert(t==1); return find(1,0,n,x);}
};

ll n,t[MAXN],tot=0; //MCH
STree cnt,bs;

ll query(ll x, STree& st){
    ll res=0;
    while(x!=-1){
        res=oper(st.query(pos[head[x]],pos[x]+1),res,st.t);
        x=fa[head[x]];
    }
    return res;
}
void upd(ll x, ll v){
	while(x!=-1){
		//cout<<x<<" "<<v<<": "<<pos[head[x]]<<","<<pos[x]+1<<": ["<<head[x]<<","<<x<<"] += "<<v<<"\n";
        cnt.upd(pos[head[x]],pos[x]+1,v);
        bs.upd(pos[head[x]],pos[x]+1,v);
        x=fa[head[x]];
    }
}
void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> W, std::vector<int> T) {
	n=N;
	fore(i,0,n){
		if(i<n-1){
			//cout<<i<<": "<<U[i]<<"-"<<V[i]<<" "<<W[i]<<endl;
			g[U[i]].pb({V[i],W[i]});
			g[V[i]].pb({U[i],W[i]});
		}
		t[i]=T[i];
	}
	hld_init();
	cnt=STree(n,0),bs=STree(n,1);
	upd(0,1); tot++;
	/*fore(i,0,n){
		cout<<"head "<<i<<": "<<head[i]<<"\n";
	}*/
	fore(i,0,n){
		upd(i,t[i]);
		tot+=t[i];
	}
	return;
}

long long max_time(int x, int v) {
	v=-t[x]+v;
	t[x]+=v;
	tot+=v;
	upd(x,v);
	/*fore(i,0,n)cout<<t[i]<<" ";
	cout<<"\n";
	cout<<"cnt\n";
	fore(i,0,n)cout<<i<<" ("<<ipos[i]<<"): "<<cnt.query(i,i+1)<<"\n";*/
	ll res=cnt.query(0,n);
	ll p=bs.find(tot/2);
	/*fore(i,0,4*n+5){
		cout<<i<<": "<<bs.st[i]<<" "<<bs.lazy[i]<<"\n";
	}
	cout<<"bs\n";
	fore(i,0,n)cout<<i<<" ("<<ipos[i]<<"): "<<bs.query(i,i+1)<<"\n";
	cout<<tot/2<<" "<<p<<"\n";*/
	res=res-2*query(p,cnt)+tot*sw[p];
	//cout<<res<<"-2*"<<query(p,cnt)<<"+"<<tot<<"*"<<sw[p]<<" = "<<res<<"\n";
	//cout<<"\n";
	return res*2;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 16208 KB Output is correct
2 Correct 80 ms 15952 KB Output is correct
3 Correct 78 ms 16208 KB Output is correct
4 Correct 80 ms 16100 KB Output is correct
5 Correct 78 ms 16208 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 3 ms 9052 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 4 ms 9140 KB Output is correct
6 Correct 3 ms 9052 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9140 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 5 ms 9052 KB Output is correct
12 Correct 4 ms 9048 KB Output is correct
13 Correct 4 ms 9048 KB Output is correct
14 Correct 3 ms 9052 KB Output is correct
15 Correct 3 ms 8900 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 16208 KB Output is correct
2 Correct 80 ms 15952 KB Output is correct
3 Correct 78 ms 16208 KB Output is correct
4 Correct 80 ms 16100 KB Output is correct
5 Correct 78 ms 16208 KB Output is correct
6 Correct 2 ms 8912 KB Output is correct
7 Correct 10 ms 9052 KB Output is correct
8 Correct 148 ms 11836 KB Output is correct
9 Correct 2480 ms 36348 KB Output is correct
10 Correct 2429 ms 36388 KB Output is correct
11 Correct 2332 ms 36392 KB Output is correct
12 Correct 2023 ms 37840 KB Output is correct
13 Correct 2015 ms 37844 KB Output is correct
14 Correct 2057 ms 37672 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 16208 KB Output is correct
2 Correct 80 ms 15952 KB Output is correct
3 Correct 78 ms 16208 KB Output is correct
4 Correct 80 ms 16100 KB Output is correct
5 Correct 78 ms 16208 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 4 ms 9052 KB Output is correct
8 Correct 38 ms 12368 KB Output is correct
9 Correct 470 ms 42628 KB Output is correct
10 Correct 486 ms 42636 KB Output is correct
11 Correct 480 ms 42636 KB Output is correct
12 Correct 488 ms 44336 KB Output is correct
13 Correct 487 ms 44508 KB Output is correct
14 Correct 427 ms 42632 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 16208 KB Output is correct
2 Correct 80 ms 15952 KB Output is correct
3 Correct 78 ms 16208 KB Output is correct
4 Correct 80 ms 16100 KB Output is correct
5 Correct 78 ms 16208 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 3 ms 9052 KB Output is correct
8 Correct 3 ms 9052 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Correct 4 ms 9140 KB Output is correct
11 Correct 3 ms 9052 KB Output is correct
12 Correct 3 ms 9052 KB Output is correct
13 Correct 3 ms 9140 KB Output is correct
14 Correct 3 ms 9052 KB Output is correct
15 Correct 3 ms 9052 KB Output is correct
16 Correct 5 ms 9052 KB Output is correct
17 Correct 4 ms 9048 KB Output is correct
18 Correct 4 ms 9048 KB Output is correct
19 Correct 3 ms 9052 KB Output is correct
20 Correct 3 ms 8900 KB Output is correct
21 Correct 2 ms 8912 KB Output is correct
22 Correct 10 ms 9052 KB Output is correct
23 Correct 148 ms 11836 KB Output is correct
24 Correct 2480 ms 36348 KB Output is correct
25 Correct 2429 ms 36388 KB Output is correct
26 Correct 2332 ms 36392 KB Output is correct
27 Correct 2023 ms 37840 KB Output is correct
28 Correct 2015 ms 37844 KB Output is correct
29 Correct 2057 ms 37672 KB Output is correct
30 Correct 2 ms 8796 KB Output is correct
31 Correct 4 ms 9052 KB Output is correct
32 Correct 38 ms 12368 KB Output is correct
33 Correct 470 ms 42628 KB Output is correct
34 Correct 486 ms 42636 KB Output is correct
35 Correct 480 ms 42636 KB Output is correct
36 Correct 488 ms 44336 KB Output is correct
37 Correct 487 ms 44508 KB Output is correct
38 Correct 427 ms 42632 KB Output is correct
39 Correct 2 ms 8796 KB Output is correct
40 Correct 5 ms 9052 KB Output is correct
41 Correct 45 ms 12316 KB Output is correct
42 Correct 723 ms 39856 KB Output is correct
43 Correct 644 ms 40756 KB Output is correct
44 Correct 643 ms 41356 KB Output is correct
45 Correct 564 ms 41860 KB Output is correct
46 Correct 526 ms 42292 KB Output is correct
47 Correct 632 ms 41424 KB Output is correct
48 Correct 568 ms 42292 KB Output is correct
49 Correct 628 ms 42872 KB Output is correct
50 Correct 492 ms 43312 KB Output is correct
51 Correct 599 ms 43852 KB Output is correct
52 Correct 1570 ms 37324 KB Output is correct
53 Correct 1422 ms 37328 KB Output is correct
54 Correct 1380 ms 37320 KB Output is correct
55 Correct 521 ms 41680 KB Output is correct
56 Correct 478 ms 42196 KB Output is correct
57 Correct 477 ms 42088 KB Output is correct