oj.uz

Submission #1013388

# Submission time Handle Problem Language Result Execution time Memory
1013388 2024-07-03T13:45:21 Z GrindMachine Designated Cities (JOI19_designated_cities) C++17
23 / 100
 2000 ms 34380 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));
    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;
    }

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15964 KB Output is correct
2 Correct 6 ms 15964 KB Output is correct
3 Correct 11 ms 15964 KB Output is correct
4 Correct 6 ms 15964 KB Output is correct
5 Correct 6 ms 16168 KB Output is correct
6 Correct 7 ms 15964 KB Output is correct
7 Correct 7 ms 16052 KB Output is correct
8 Correct 6 ms 15964 KB Output is correct
9 Correct 6 ms 15960 KB Output is correct
10 Correct 12 ms 16220 KB Output is correct
11 Correct 9 ms 16048 KB Output is correct

Subtask #2
0 / 7.0

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

Subtask #3
0 / 9.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15964 KB Output is correct
2 Correct 6 ms 15964 KB Output is correct
3 Correct 11 ms 15964 KB Output is correct
4 Correct 6 ms 15964 KB Output is correct
5 Correct 6 ms 16168 KB Output is correct
6 Correct 7 ms 15964 KB Output is correct
7 Correct 7 ms 16052 KB Output is correct
8 Correct 6 ms 15964 KB Output is correct
9 Correct 6 ms 15960 KB Output is correct
10 Correct 12 ms 16220 KB Output is correct
11 Correct 9 ms 16048 KB Output is correct
12 Correct 6 ms 15964 KB Output is correct
13 Correct 38 ms 16352 KB Output is correct
14 Correct 48 ms 16440 KB Output is correct
15 Correct 37 ms 16340 KB Output is correct
16 Correct 52 ms 16220 KB Output is correct
17 Correct 55 ms 16216 KB Output is correct
18 Correct 47 ms 16356 KB Output is correct
19 Correct 35 ms 16348 KB Output is correct
20 Correct 35 ms 16216 KB Output is correct
21 Correct 45 ms 16468 KB Output is correct
22 Correct 43 ms 16220 KB Output is correct
23 Correct 35 ms 16344 KB Output is correct
24 Correct 22 ms 16300 KB Output is correct
25 Correct 49 ms 16468 KB Output is correct
26 Correct 22 ms 16220 KB Output is correct

Subtask #5
0 / 17.0

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

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15964 KB Output is correct
2 Correct 6 ms 15964 KB Output is correct
3 Correct 11 ms 15964 KB Output is correct
4 Correct 6 ms 15964 KB Output is correct
5 Correct 6 ms 16168 KB Output is correct
6 Correct 7 ms 15964 KB Output is correct
7 Correct 7 ms 16052 KB Output is correct
8 Correct 6 ms 15964 KB Output is correct
9 Correct 6 ms 15960 KB Output is correct
10 Correct 12 ms 16220 KB Output is correct
11 Correct 9 ms 16048 KB Output is correct
12 Correct 7 ms 15960 KB Output is correct
13 Execution timed out 2081 ms 34380 KB Time limit exceeded
14 Halted 0 ms 0 KB -