Submission #1175832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175832		Warinchai	Designated Cities (JOI19_designated_cities)	C++20	7 / 100	127 ms	37772 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];
int val[200005];
int sum[200005];
int tans[200005];
int ans[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);
    }
}
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}});
        all+=c+d;
    }
    int q;cin>>q;
    dfs(1,0);
    reroot(1,0,0);
    for(int i=1;i<=n;i++)ans[i]=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: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44