Submission #1175880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175880		Warinchai	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	303 ms	41124 KiB

designated_cities

#include<bits/stdc++.h>
#define int long long
using namespace std;
int inf=1e18;
vector<pair<int,pair<int,int>>>adj[200005];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
int val[200005];
int sum[200005];
int tans[200005];
int ans[200005];
int used[200005];
int all=0;
void dfs(int u,int p){
    for(auto x:adj[u]){
        if(x.first==p)val[u]+=x.second.first,sum[u]-=x.second.first;
        else{
            dfs(x.first,u);
            val[u]+=val[x.first];
        }
    }
    sum[u]+=val[u];
}
void reroot(int u,int p,int ans){
    //cerr<<u<<" "<<sum[u]<<" "<<ans<<"\n";
    tans[u]=sum[u]+ans;
    for(auto x:adj[u]){
        if(x.first!=p)reroot(x.first,u,ans+sum[u]-val[x.first]+x.second.first);
    }
}
int deg[200005];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<n;i++){
        int a,b,c,d;cin>>a>>b>>c>>d;
        adj[a].push_back({b,{c,d}});
        adj[b].push_back({a,{d,c}});
        deg[a]++,deg[b]++;
        all+=c+d;
    }
    int q;cin>>q;
    dfs(1,0);
    reroot(1,0,0);
    for(int i=1;i<=n;i++)if(deg[i]==1)pq.push({adj[i][0].second.second,i});
    while(!pq.empty()){
        int cost=pq.top().first;
        int x=pq.top().second;
        //cerr<<x<<"\n";
        pq.pop();
        used[x]=1;
        int nxt;
        for(auto v:adj[x])if(!used[v.first])nxt=v.first;
        if(--deg[nxt]==1){
            int e=0;
            for(auto v:adj[nxt])if(!used[v.first])e=v.second.second;
            pq.push({cost+e,nxt});
        }else{
            //cerr<<"del:"<<cost<<"\n";
            ans[pq.size()]=ans[pq.size()+1]+cost;
        }
    }
    ans[1]=inf;
    for(int i=1;i<=n;i++){
        ans[1]=min(ans[1],all-tans[i]);
    }
    for(int i=0;i<q;i++){
        int x;cin>>x;
        cout<<ans[x]<<"\n";
    }
}

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