Submission #107798

#	Time	Username	Problem	Language	Result	Execution time	Memory
107798		shayan_p	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	761 ms	64752 KiB

designated_cities

// Faster!

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=2e5+10,mod=1e9+7;
const ll inf=1e17;

vector< pair<int,pii> >v[maxn];
ll ans[maxn],f[maxn],g[maxn],Tot;
pair<int,ll>pr[maxn];

int n;
ll mx[maxn];
int mxid[maxn];

pii seg[maxn];
int C,reseg[maxn];

bool in[maxn];

ll val[4*maxn],lz[4*maxn];
int who[4*maxn];

void _merge(int id){
    val[id]=max(val[2*id],val[2*id+1]);
    if(val[2*id]==val[id]) who[id]=who[2*id];
    else who[id]=who[2*id+1];
}
void shift(int l,int r,int id){
    val[id]+=lz[id];
    if(r-l>1){
	lz[2*id]+=lz[id];
	lz[2*id+1]+=lz[id];
    }
    lz[id]=0;
}
void build(int l=0,int r=n,int id=1){
    lz[id]=0;
    if(r-l==1){
	who[id]=reseg[l];
	val[id]=f[reseg[l]];
	return;
    }
    int mid=(l+r)>>1;
    build(l,mid,2*id);
    build(mid,r,2*id+1);
    _merge(id);
}
int ask(){
    shift(0,n,1);
    if(val[1]<=0) return -1;
    return who[1];
}
void put(int pos,ll x,int l=0,int r=n,int id=1){
    shift(l,r,id);
    if(r-l==1){
	val[id]=x;
	return;
    }
    int mid=(l+r)>>1;
    if(pos<mid) put(pos,x,l,mid,2*id), shift(mid,r,2*id+1);
    else put(pos,x,mid,r,2*id+1), shift(l,mid,2*id);
    _merge(id);
}
void add(int f,int s,ll x,int l=0,int r=n,int id=1){
    if(f>=s || l>=r) return;
    shift(l,r,id);
    if(s<=l || r<=f) return;
    if(f<=l && r<=s) { lz[id]=x; shift(l,r,id); return; }
    int mid=(l+r)>>1;
    add(f,s,x,l,mid,2*id);
    add(f,s,x,mid,r,2*id+1);
    _merge(id);
}

void prep(int u,int par=-1){
    mx[u]=f[u],mxid[u]=u;
    seg[u].F=C, reseg[C]=u, C++;
    for(auto p:v[u]){
	if(p.F!=par){
	    f[p.F]=f[u]+p.S.F;
	    g[p.F]=g[u]+p.S.S;
	    Tot+=p.S.F;
	    pr[p.F]={u,p.S.F};
	    
	    prep(p.F,u);
	    
	    if(mx[p.F]>mx[u]){
		mx[u]=mx[p.F];
		mxid[u]=mxid[p.F];
	    }
	}
    }
    seg[u].S=C;
}

pair<ll,pii> choose(int u,int par=-1){
    pair<ll,pii> ans={Tot-mx[u]+g[u],{u,mxid[u]}};
    pair<ll,int> pp={-1,-1};
    for(auto p:v[u]){
	if(p.F!=par){
	    ans=min(ans,choose(p.F,u));
	    if(pp.F!=-1) ans=min(ans, (pair<ll,pii>){Tot-mx[p.F]-pp.F+f[u]+g[u], {mxid[p.F],pp.S} } );
	    pp=max(pp, (pair<ll,int>){mx[p.F],mxid[p.F]} );
	}
    }
    return ans;
}

void solve(int u){
    f[u]=g[u]=Tot=C=0,prep(u);
    memset(in,0,sizeof in);
    in[u]=1;
    build();
    int pt=1;
    while(ask()!=-1){
	int tmp=ask();
	while(in[tmp]==0){
	    add(seg[tmp].F,seg[tmp].S,-pr[tmp].S);
	    put(seg[tmp].F,0);
	    Tot-=pr[tmp].S;
	    in[tmp]=1;
	    tmp=pr[tmp].F;
	}
	++pt,ans[pt]=min(ans[pt],Tot);
    }
    while(pt<n){
	++pt,ans[pt]=min(ans[pt],Tot);
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    fill(ans,ans+n+1,inf);
    for(int i=0;i<n-1;i++){
	int a,b,c,d;cin>>a>>b>>c>>d;
	--a,--b;
	v[a].PB({b,{c,d}});
	v[b].PB({a,{d,c}});
    }
    prep(0);
    for(int i=0;i<n;i++){
	ans[1]=min(ans[1],Tot-f[i]+g[i]);
    }
    pii p=choose(0).S;
    solve(p.F);
    int q;cin>>q;
    while(q--){
	int x;cin>>x;
	cout<<ans[x]<<"\n";
    }
    return 0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44