oj.uz

Submission #1013383

# Submission time Handle Problem Language Result Execution time Memory
1013383 2024-07-03T13:37:34 Z GrindMachine Designated Cities (JOI19_designated_cities) C++17
0 / 100
 2000 ms 32436 KB 
#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;
}

ll curr_sum = 0;

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

void go(ll u){
    nodes.clear();
    dfs1(u,-1,-1);
    ll c = dfs2(u,-1,sz(nodes));
    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;
            }
        }

        first = -1;

        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[u] = 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;
    }

    rep1(i,n){
        curr_sum = 0;
        dfs3(i,-1);
        in_sum[i] = curr_sum;
    }

    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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15964 KB Output is correct
2 Incorrect 7 ms 15912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15964 KB Output is correct
2 Execution timed out 2058 ms 32436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15960 KB Output is correct
2 Execution timed out 2091 ms 29208 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15964 KB Output is correct
2 Incorrect 7 ms 15912 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15964 KB Output is correct
2 Execution timed out 2058 ms 32436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15964 KB Output is correct
2 Incorrect 7 ms 15912 KB Output isn't correct
3 Halted 0 ms 0 KB -