Submission #1209020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209020		Hanksburger	Designated Cities (JOI19_designated_cities)	C++20	7 / 100	1303 ms	63352 KiB

designated_cities

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<pair<int, pair<int, int> > > adj[200005];
int ans[200005], sumsum, cnt;
void dfs1(unordered_map<int, int> &mp, vector<int> &sz, int u, int p)
{
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first;
        if (v==p || !mp[v])
            continue;
        dfs1(mp, sz, v, u);
        sz[mp[u]]+=sz[mp[v]];
    }
}
int dfs2(unordered_map<int, int> &mp, vector<int> &sz, int u, int p, int n)
{
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first;
        if (v==p || !mp[v])
            continue;
        if (sz[mp[v]]*2>n)
            return dfs2(mp, sz, v, u, n);
    }
    return u;
}
vector<int> *dfs3(unordered_map<int, int> &mp, int u, int p)
{
    vector<int> *ans=new vector<int>;
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first, w=adj[u][i].second.first;
        if (v==p || !mp[v])
            continue;
        vector<int> *res=dfs3(mp, v, u);
        (*res)[0]+=w;
        if (ans->size()<res->size())
            swap(ans, res);
        if (res->empty())
        {
            delete res;
            continue;
        }
        if ((*ans)[0]<(*res)[0])
            swap((*ans)[0], (*res)[0]);
        for (int x:*res)
            ans->push_back(x);
        delete res;
    }
    if (ans->empty())
        ans->push_back(0);
    //cout << u << ": ";
    //for (int x:*ans)
    //    cout << x << ' ';
    //cout << '\n';
    return ans;
}
void dfs4(unordered_map<int, int> &mp, vector<int> &sum, int u, int p)
{
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first, w=adj[u][i].second.first;
        if (v==p || !mp[v])
            continue;
        dfs4(mp, sum, v, u);
        sum[mp[u]]+=sum[mp[v]]+w;
    }
}
void dfs5(unordered_map<int, int> &mp, vector<int> &tmp, int u, int p)
{
    //cout << "dfs5 " << u << '\n';
    tmp.push_back(u);
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first;
        if (v==p || !mp[v])
            continue;
        dfs5(mp, tmp, v, u);
    }
}
void recur(vector<int> &vec, int offset)
{
    int n=vec.size();
    if (n<=2)
        return;
    //cout << "recur ";
    //for (int x:vec)
    //    cout << x << ' ';
    //cout << '\n';
    unordered_map<int, int> mp;
    vector<pair<int, int> > dp;
    vector<int> sum(n+1, 0), sz(n+1, 1);
    for (int i=0; i<n; i++)
        mp[vec[i]]=i+1;
    dfs1(mp, sz, vec[0], 0);
    int centroid=dfs2(mp, sz, vec[0], 0, n);
    //cout << "centroid = " << centroid << '\n';
    for (int i=0; i<adj[centroid].size(); i++)
    {
        int v=adj[centroid][i].first, w=adj[centroid][i].second.first;
        if (!mp[v])
            continue;
        vector<int> *res=dfs3(mp, v, centroid);
        (*res)[0]+=w;
        for (int x:*res)
            dp.push_back({x, i});
        delete res;
    }
    //cout << "here\n";
    sort(dp.begin(), dp.end(), greater<pair<int, int> >());
    dfs4(mp, sum, centroid, 0);
    int cur=0, ind=0;
    //cout << "dp: ";
    //for (int i=0; i<dp.size(); i++)
    //{
    //    cout << dp[i].first << ' ' << dp[i].second << '\n';
    //}
    for (int i=1; i<dp.size(); i++)
    {
        if (dp[i-1].second!=dp[i].second)
        {
            ind=i;
            break;
        }
    }
    //cout << "sum = " << sum[mp[centroid]] << '\n';
    for (int i=2; i<=dp.size(); i++)
    {
        cur+=dp[i-2].first;
        ans[i]=min(ans[i], sum[mp[centroid]]-cur-dp[max(ind, i-1)].first+offset);
    }
    //cout << "here\n";
    for (int i=0; i<adj[centroid].size(); i++)
    {
        //cout << "i=" << i << '\n';
        int v=adj[centroid][i].first, w1=adj[centroid][i].second.first, w2=adj[centroid][i].second.second;
        if (!mp[v])
            continue;
        vector<int> tmp;
        dfs5(mp, tmp, v, centroid);
        recur(tmp, offset+sum[mp[centroid]]-sum[mp[v]]-w1+w2);
    }
}
void calc1(int u, int p)
{
    int leaf=1;
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first, w=adj[u][i].second.first;
        if (v==p)
            continue;
        calc1(v, u);
        sumsum+=w;
        leaf=0;
    }
    if (leaf)
        cnt++;
}
void calc2(int u, int p, int offset)
{
    ans[1]=min(ans[1], offset);
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first, w1=adj[u][i].second.first, w2=adj[u][i].second.second;
        if (v==p)
            continue;
        calc2(v, u, offset-w1+w2);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n;
    for (int i=1; i<n; i++)
    {
        int u, v, w1, w2;
        cin >> u >> v >> w1 >> w2;
        adj[u].push_back({v, {w1, w2}});
        adj[v].push_back({u, {w2, w1}});
    }
    vector<int> tmp(n);
    for (int i=1; i<=n; i++)
        tmp[i-1]=i, ans[i]=1e18;
    recur(tmp, 0);
    calc1(1, 0);
    calc2(1, 0, sumsum);
    for (int i=cnt+1; i<=n; i++)
        ans[i]=ans[cnt];
    cin >> q;
    for (int i=1; 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