oj.uz

Submission #687694

# Submission time Handle Problem Language Result Execution time Memory
687694 2023-01-26T21:17:58 Z QwertyPi Paths (RMI21_paths) C++14
56 / 100
 600 ms 18636 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define int long long
using namespace std;

const int MAXN = 1e5 + 11;
vector<pair<int, int>> G[MAXN];
int w[MAXN], mx_dis[MAXN];
int to[MAXN], a[MAXN], l[MAXN], r[MAXN];
int leaf_cnt = 0;
void dfs(int v, int pa = -1){
    int sons_cnt = 0;
    l[v] = MAXN, r[v] = -1;
    for(auto& [u, we] : G[v]){
        if(u != pa){
            sons_cnt++;
            w[u] = we; dfs(u, v);
            if(mx_dis[u] + w[u] > mx_dis[v]){
                to[v] = to[u];
                mx_dis[v] = mx_dis[u] + w[u];
            }
            l[v] = min(l[v], l[u]), r[v] = max(r[v], r[u]);
        }
    }
    if(sons_cnt == 0){
        to[v] = ++leaf_cnt; l[v] = r[v] = leaf_cnt;
    }
    a[to[v]] += w[v];
}

namespace Treap{

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    struct node{
        int key, size, sum, prior;
        node *ll, *rr;
        node(int key) : key(key), size(1), sum(key), prior(rng()), ll(nullptr), rr(nullptr) {};
    };

    int size(node* t){
        return t ? t->size : 0;
    }
    int sum(node* t){
        return t ? t->sum : 0;
    }
    void maintain(node*& t){
        if(!t) return;
        t->size = size(t->ll) + 1 + size(t->rr);
        t->sum = sum(t->ll) + t->key + sum(t->rr);
    }
    void _crawl(node* t){
        if(!t) return;
        if(t->ll) _crawl(t->ll);
        cout << t->key << ' ';
        if(t->rr) _crawl(t->rr);
    }
    void crawl(node* t){
        _crawl(t); cout << endl;
    }
    void split_size(node* t, node*& l, node*& r, int l_size){
        if(!t) return void(l = r = nullptr);
        if(size(t->ll) >= l_size) split_size(t->ll, l, t->ll, l_size), r = t;
        else split_size(t->rr, t->rr, r, l_size - size(t->ll) - 1), l = t;
        maintain(l); maintain(r);
    }
    void split_key(node* t, node*& l, node*& r, int key){
        if(!t) return void(l = r = nullptr);
        if(t->key >= key) split_key(t->ll, l, t->ll, key), r = t;
        else split_key(t->rr, t->rr, r, key), l = t; 
        maintain(l); maintain(r);
    }
    void merge(node*& t, node* l, node* r){
        if(!l || !r) t = l ? l : r;
        else if(l->prior > r->prior) merge(l->rr, l->rr, r), t = l;
        else merge(r->ll, l, r->ll), t = r;
        maintain(t);
    }
    node* subtree_min(node* t){
        while(t->ll) t = t->ll;
        return t;
    }
    node *a = nullptr;
    void add(int key){
        node *l, *v, *r;
        v = new node(key);
        split_key(a, l, r, key);
        merge(r, v, r);
        merge(a, l, r);
    }
    void erase(int key){
        node *l, *m, *r;
        split_key(a, l, m, key);
        split_size(m, m, r, 1);
        delete m;
        merge(a, l, r);
    }
    int kth_max_sum(int k){
        node *l, *r;
        split_size(a, l, r, max(0LL, size(a) - k));
        int res = sum(r);
        merge(a, l, r);
        return res;
    }
};

namespace Segtree{
    int t[MAXN << 2], a[MAXN];
    int cmp(int q1, int q2){
        if(q1 == MAXN - 1 || q2 == MAXN - 1) return q1 == MAXN - 1 ? q2 : q1;
        else return a[q1] > a[q2] ? q1 : q2;
    }
    void upd(int i, int va, int v, int l, int r){
        if(l == r) { a[i] = va; t[v] = i; return; }
        int m = (l + r) >> 1;
        if(i <= m) upd(i, va, v * 2 + 1, l, m);
        else upd(i, va, v * 2 + 2, m + 1, r);
        t[v] = cmp(t[v * 2 + 1], t[v * 2 + 2]);
    }
    int qry_max(int ql, int qr, int v, int l, int r){
        if(qr < l || r < ql) return MAXN - 1;
        if(ql <= l && r <= qr) return t[v];
        int m = (l + r) >> 1;
        int q1 = qry_max(ql, qr, v * 2 + 1, l, m);
        int q2 = qry_max(ql, qr, v * 2 + 2, m + 1, r);
        return cmp(q1, q2);
    }
};

int ans[MAXN]; int N, K; 
void dfs2(int v, int pa = -1){
    ans[v] = Treap::kth_max_sum(K);
    for(auto& [u, we] : G[v]){
        if(u != pa){
            using Segtree::a;
            int bl = 1, br = leaf_cnt, sl = l[u], sr = r[u];
            int q1 = Segtree::qry_max(bl, sl - 1, 0, 1, leaf_cnt), q2 = Segtree::qry_max(sr + 1, br, 0, 1, leaf_cnt);
            int qo = Segtree::cmp(q1, q2); Treap::erase(a[qo]); Treap::add(a[qo] + w[u]); Segtree::upd(qo, a[qo] + w[u], 0, 1, leaf_cnt);
            int qn = Segtree::qry_max(sl, sr, 0, 1, leaf_cnt); Treap::erase(a[qn]); Treap::add(a[qn] - w[u]); Segtree::upd(qn, a[qn] - w[u], 0, 1, leaf_cnt);
            dfs2(u, v);
            Treap::erase(a[qo]); Treap::add(a[qo] - w[u]); Segtree::upd(qo, a[qo] - w[u], 0, 1, leaf_cnt);
            Treap::erase(a[qn]); Treap::add(a[qn] + w[u]); Segtree::upd(qn, a[qn] + w[u], 0, 1, leaf_cnt);
        }
    }
}

int32_t main(){
    cin >> N >> K; int sum_w = 0;
    for(int i = 0; i < N - 1; i++){
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
        sum_w += w;
    }
    
    if(N == 2){
        cout << sum_w << endl;
        return 0;
    }

    int rt = 1;
    if(G[rt].size() == 1) rt = G[rt][0].first;
    dfs(rt);
    for(int i = 1; i <= leaf_cnt; i++) Treap::add(a[i]);
    for(int i = 1; i <= leaf_cnt; i++) Segtree::upd(i, a[i], 0, 1, leaf_cnt);
    dfs2(rt);
    for(int i = 1; i <= N; i++) cout << ans[i] << endl;
}

Compilation message

Main.cpp: In function 'void dfs(long long int, long long int)':
Main.cpp:15:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |     for(auto& [u, we] : G[v]){
      |               ^
Main.cpp: In function 'void dfs2(long long int, long long int)':
Main.cpp:133:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  133 |     for(auto& [u, we] : G[v]){
      |               ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 7 ms 2848 KB Output is correct
9 Correct 5 ms 2900 KB Output is correct
10 Correct 5 ms 2772 KB Output is correct
11 Correct 6 ms 2772 KB Output is correct
12 Correct 6 ms 2824 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 7 ms 2848 KB Output is correct
9 Correct 5 ms 2900 KB Output is correct
10 Correct 5 ms 2772 KB Output is correct
11 Correct 6 ms 2772 KB Output is correct
12 Correct 6 ms 2824 KB Output is correct
13 Correct 10 ms 3028 KB Output is correct
14 Correct 10 ms 3028 KB Output is correct
15 Correct 9 ms 2900 KB Output is correct
16 Correct 11 ms 3028 KB Output is correct
17 Correct 10 ms 2900 KB Output is correct
18 Correct 9 ms 2900 KB Output is correct
19 Correct 11 ms 2900 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 682 ms 18636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 7 ms 2848 KB Output is correct
9 Correct 5 ms 2900 KB Output is correct
10 Correct 5 ms 2772 KB Output is correct
11 Correct 6 ms 2772 KB Output is correct
12 Correct 6 ms 2824 KB Output is correct
13 Correct 10 ms 3028 KB Output is correct
14 Correct 10 ms 3028 KB Output is correct
15 Correct 9 ms 2900 KB Output is correct
16 Correct 11 ms 3028 KB Output is correct
17 Correct 10 ms 2900 KB Output is correct
18 Correct 9 ms 2900 KB Output is correct
19 Correct 11 ms 2900 KB Output is correct
20 Execution timed out 682 ms 18636 KB Time limit exceeded
21 Halted 0 ms 0 KB -