Submission #376810

#	Time	Username	Problem	Language	Result	Execution time	Memory
376810		jass921026	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	478 ms	50924 KiB

designated_cities

#include<bits/stdc++.h>
using namespace std;
#define jizz ios_base::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef pair<ll,ll> pii;
#define F first
#define S second
const int MAXN=2E5+10;
vector<pii> G[MAXN];
ll sum[MAXN], sum2[MAXN], path[MAXN], nxt[MAXN], ans[MAXN];
void init(int x, int f){
    for(auto i:G[x]){
        if(i.F!=f){
            init(i.F,x);
        } else{
            sum[1]+=i.S;
        }
    }
}
void getSum(int x, int f, ll s){
    ll maxpath=0, secpath=0;
    for(auto i:G[x]){
        if(i.F==f){
            sum[x]=s-i.S;
            break;
        }
    }
    for(auto i:G[x]){
        if(i.F!=f){
            getSum(i.F,x,sum[x]+i.S);
            ll cp=path[i.F]+i.S;
            if(cp>maxpath){
                nxt[x]=i.F;
                secpath=maxpath;
                maxpath=cp;
            } else{
                secpath=max(secpath,cp);
            }
        }
    }
    path[x]=maxpath;
    sum2[x]=sum[x]+maxpath+secpath;
}
void getNewPath(int x, int f){
    for(auto i:G[x]){
        if(i.F!=f){
            getNewPath(i.F,x);
            ll cp=path[i.F]+i.S;
            if(cp>path[x]){
                path[x]=cp;
                nxt[x]=i.F;
            }
        }
    }
}
priority_queue<ll> pq;
void getPQ(int x, int f, int t, ll s){
    if(x==t) pq.push(s+path[x]);
    for(auto i:G[x]){
        if(i.F==nxt[x]){
            getPQ(i.F,x,t,i.S);
        }
        else if(i.F!=f){
            getPQ(i.F,x,i.F,i.S);
        }
    }
}
int main(){ jizz
    int n;
    cin>>n;
    ll all=0;
    for(int i=0;i<n-1;i++){
        int a, b, c, d;
        cin>>a>>b>>c>>d;
        G[a].push_back({b,c});
        G[b].push_back({a,d});
        all=all+c+d;
    }
    init(1,0);
    getSum(1,0,sum[1]);
    int newroot=0;
    for(int i=1;i<=n;i++){
        ans[1]=max(ans[1],sum[i]);
        if(sum2[i]>ans[2]){
            ans[2]=sum2[i];
            newroot=i;
        }
    }
    while(nxt[newroot]) newroot=nxt[newroot];
    for(int i=1;i<=n;i++){
        path[i]=0;
        nxt[i]=0;
    }
    //cout<<"nr "<<newroot<<"\n";
    getNewPath(newroot,0);
    getPQ(newroot,0,newroot,0);
    pq.pop();
    for(int i=3;i<=n;i++){
        if(!pq.empty()){
            ans[i]=ans[i-1]+pq.top();
            pq.pop();
        } else{
            ans[i]=all;
        }
    }
    int q;
    cin>>q;
    for(int i=0;i<q;i++){
        int e;
        cin>>e;
        cout<<all-ans[e]<<"\n";
    }
    return 0;
}
/*
6
1 6 6 12
6 2 5 16
1 4 13 4
5 1 19 3
3 1 9 13
3
1
2
3
*/

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