제출 #959756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959756		Tuanlinh123	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	325 ms	77536 KiB

designated_cities

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

struct edge
{
    ll v, c, d;
    edge(){}
    edge(ll v, ll c, ll d): v(v), c(c), d(d){}
};

const ll maxn=200005;
priority_queue <ll> q[maxn];
ll ans[maxn], C[maxn], D[maxn];
pair<pll, pll> dp[maxn];
vector <edge> A[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, sum=0, allup=0, root=0, crm=0; cin >> n;
    for (ll i=1; i<n; i++)
    {
        ll u, v, c, d; cin >> u >> v >> c >> d;
        A[u].pb({v, c, d}), A[v].pb({u, d, c});
        sum+=c, sum+=d;
    }
    function <void(ll, ll)> dfs=[&](ll u, ll pa)
    {
        ans[1]=max(ans[1], C[u]-D[u]), dp[u].fi={0, u};
        for (auto [v, c, d]:A[u])
        {
            if (v==pa) continue;
            C[v]=C[u]+c, D[v]=D[u]+d, allup+=d, dfs(v, u);
            pll val={dp[v].fi.fi+c, dp[v].fi.se};
            if (val>dp[u].fi) dp[u].se=dp[u].fi, dp[u].fi=val;
            else if (val>dp[u].se) dp[u].se=val;
        }
        ll val=C[u]-D[u]+dp[u].fi.fi+dp[u].fi.se;
        if (val>crm) root=dp[u].fi.se, crm=val;
    }; dfs(1, 1), ans[1]=sum-(ans[1]+allup), allup=0;
    function <void(ll, ll)> dfs2=[&](ll u, ll pa)
    {   
        vector <ll> num;
        for (auto [v, c, d]:A[u])
        {
            if (v==pa) continue;
            C[v]=C[u]+c, allup+=d;
            dfs2(v, u), num.pb(q[v].top()), q[v].pop();
        }
        if (!sz(num)) {q[u].push(C[u]); return;}
        sort(num.begin(), num.end(), greater<ll>());
        for (ll i=0; i<sz(num); i++)
            q[u].push(i?num[i]-C[u]:num[i]);
        for (auto [v, c, d]:A[u])
            if (v!=pa)
            {
                if (sz(q[u])<sz(q[v])) swap(q[u], q[v]);
                while (sz(q[v])) q[u].push(q[v].top()), q[v].pop();
            }
    }; C[root]=0, dfs2(root, root);
    for (ll i=2, s=0; i<=n; i++)
    {
        if (q[root].empty()) {ans[i]=ans[i-1]; continue;}
        s+=q[root].top(), q[root].pop();
        ans[i]=sum-(allup+s);
    }
    ll q; cin >> q;
    while (q--) {ll 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