Submission #1013391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013391		GrindMachine	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	887 ms	59712 KiB

designated_cities

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/66022?#comment-501121

*/

const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<array<ll,3>> adj[N];
vector<pll> farthest(N);
vector<ll> leaf_add(N);
vector<ll> ans(N);
vector<ll> sub_id(N);
vector<ll> subsiz(N);
vector<bool> rem(N);
vector<ll> in_sum(N);
vector<ll> nodes;

void dfs1(ll u, ll p, ll s){
    nodes.pb(u);
    sub_id[u] = s;
    farthest[u] = {0,u};
    leaf_add[u] = 0;
    subsiz[u] = 1;

    for(auto [v,x,y] : adj[u]){
        if(v == p or rem[v]) conts;
        dfs1(v,u,s==-1?v:s);
        subsiz[u] += subsiz[v];
        auto px = farthest[v];
        px.ff += x;
        leaf_add[px.ss] += x;
        amax(farthest[u],px);
    }
}

ll dfs2(ll u, ll p, ll nodes){
    for(auto [v,x,y] : adj[u]){
        if(v == p or rem[v]) conts;
        if(subsiz[v] > nodes/2){
            return dfs2(v,u,nodes);
        }
    }
    return u;
}

void dfs3(ll u, ll p){
    in_sum[u] = 0;
    for(auto [v,x,y] : adj[u]){
        if(v == p) conts;
        in_sum[u] += y;
        dfs3(v,u);
        in_sum[u] += in_sum[v];
    }
}

void dfs4(ll u, ll p){
    for(auto [v,x,y] : adj[u]){
        if(v == p) conts;
        in_sum[v] = in_sum[u]-y+x;
        dfs4(v,u);
    }
}

void go(ll u){
    nodes.clear();
    dfs1(u,-1,-1);
    ll c = dfs2(u,-1,sz(nodes));
    nodes.clear();
    dfs1(c,-1,-1);

    vector<pll> ord;
    trav(u,nodes){
        ord.pb({leaf_add[u],sub_id[u]});
    }
    sort(rall(ord));

    // pick centroid
    {
        ll cost = in_sum[c];
        ll pick = 1;
        amax(ans[pick],cost);

        for(auto [x,id] : ord){
            pick++;
            cost += x;
            amax(ans[pick],cost);
        }
    }

    // pick nodes (actually leaves) from at least 2 diff subtrees
    if(sz(ord) >= 2){
        ll cost = in_sum[c];
        ll pick = 1;
        ll first = -1;
        rep(i,sz(ord)){
            if(ord[i].ss != ord[0].ss){
                first = i;
                break;
            }
        }

        if(first != -1){
            cost += ord[first].ff;
            ord.erase(ord.begin()+first);

            for(auto [x,id] : ord){
                cost += x;
                pick++;
                amax(ans[pick],cost);
            }
        }
    }

    rem[c] = 1;
    for(auto [v,x,y] : adj[c]){
        if(rem[v]) conts;
        go(v);
    }
}

void solve(int test_case)
{
    ll n; cin >> n;
    ll tot_sum = 0;

    rep1(i,n-1){
        ll u,v,x,y; cin >> u >> v >> x >> y;
        adj[u].pb({v,x,y}), adj[v].pb({u,y,x});
        tot_sum += x+y;
    }

    dfs3(1,-1);
    dfs4(1,-1);

    go(1);

    rep1(i,n) ans[i] = tot_sum-ans[i];

    ll q; cin >> q;
    while(q--){
        ll k; cin >> k;
        cout << ans[k] << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

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