Submission #1175657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175657		12345678	Designated Cities (JOI19_designated_cities)	C++20	7 / 100	126 ms	35572 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e5+5;

ll n, q, u, v, a, b, used[nx], deg[nx], res[nx], up[nx], dn[nx], sm;
vector<tuple<ll ,ll, ll>> d[nx];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;

void dfs(int u, int p)
{
    for (auto [v, a, b]:d[u])
    {
        if (v==p) continue;
        up[v]=up[u]+b;
        dn[v]=dn[u]+a;
        sm+=a;
        dfs(v, u);
    }
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<n; i++) cin>>u>>v>>a>>b, d[u].push_back({v, a, b}), d[v].push_back({u, b, a}), deg[u]++, deg[v]++;
    for (int i=1; i<=n; i++) if (deg[i]==1) pq.push({0, i});
    while (pq.size()>2)
    {
        auto [w, u]=pq.top();
        pq.pop();
        used[u]=1;
        for (auto [v, a, b]:d[u])
        {
            if (!used[v])
            {
                w+=b;
                u=v;
                break;
            }
        }
        if (--deg[u]==1) pq.push({w, u});
        else res[pq.size()]=res[pq.size()+1]+w;
    }
    dfs(1, 1);
    res[1]=1e18;
    for (int i=1; i<=n; i++) res[1]=min(res[1], sm+up[i]-dn[i]);
    cin>>q;
    while (q--) cin>>u, cout<<res[u]<<'\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