Submission #1081895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081895		vjudge1	Designated Cities (JOI19_designated_cities)	C++17	0 / 100	6 ms	10076 KiB

designated_cities

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
using namespace std;
const int mxn=1e5+5;
struct dat{
    int v;ll a,b;
};vector<dat>g[mxn];
ll dp[mxn]{0},rs[mxn]{0},d[mxn]{0};
void dfs1(int u,int p){
    for(auto [v,a,b]:g[u]){
        if(v==p)continue;
        dfs1(v,u);dp[u]+=b+dp[v];
    }
}
void dfs2(int u,int p){
    for(auto [v,a,b] :g[u]){
        if(v==p)continue;
        dp[v]=dp[u]+a-b;dfs2(v,u);
    }
}int rt;
ll dfs3(int u,int p){
    ll mx1=0,mx2=0;
    for(auto [v,a,b] : g[u]){
        if(v==p)continue;
        dfs3(v,u);
        ll tt=d[v]+a;
        if(tt>mx1)swap(tt,mx1);
        if(tt>mx2)swap(tt,mx2);
    }
    if(rs[2]<mx1+mx2+dp[u]){
        rs[2]=mx1+mx2+dp[u];
        rt=u;
    }
    return d[u]=mx1;
}
vector<ll>di[mxn];
void dfs4(int u,int p,ll t){
    di[u].pb(0);
    for(auto [v,a,b] : g[u]){
        if(v==p)continue;
        dfs4(v,u,a);
        if(di[u].size()<di[v].size())swap(di[u],di[v]);
        if(di[u].back()>di[v].back())swap(di[u].back(),di[v].back());
        for(auto x:di[v])di[u].pb(x);
    }di[u].back()+=t;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;ll ans=0;
    for(int i=1;i<=n-1;i++){
        int u,v,a,b;cin>>u>>v>>a>>b;ans+=a+b;
        g[u].pb({v,a,b});g[v].pb({u,b,a});
    }dfs1(1,1);dfs2(1,1);for(int i=1;i<=n;i++)rs[1]=max(rs[1],dp[i]);
    dfs3(1,1);dfs4(rt,rt,0);sort(di[rt].rbegin(),di[rt].rend());
    ll cur = di[rt][0]+di[rt][1];
    for(int i=2;i<n;i++){
        cur+=di[rt][i];
        rs[i+1]=dp[rt]+cur;
    }int q;cin>>q;
    while(q--){
        int x;cin>>x;
        cout<<ans-rs[x]<<'\n';
    }
}

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