oj.uz

Submission #687684

# Submission time Handle Problem Language Result Execution time Memory
687684 2023-01-26T20:48:03 Z QwertyPi Paths (RMI21_paths) C++14
36 / 100
 600 ms 15712 KB 
#include <bits/stdc++.h>
#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;
    }
};

void dfs2(int v, int pa = -1){
    for(auto& [u, we] : G[v]){

    }
}

int32_t main(){
    int N, K; cin >> N >> K;
    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});
    }
 
    for(int i = 1; i <= N; i++){
        fill(a + 1, a + N + 1, 0);
        fill(mx_dis + 1, mx_dis + N + 1, 0);
        fill(w + 1, w + N + 1, 0);
        fill(to + 1, to + N + 1, 0);
        fill(l + 1, l + N + 1, 0);
        fill(r + 1, r + N + 1, 0);
        leaf_cnt = 0;
        dfs(i);
        for(int i = 1; i <= leaf_cnt; i++) Treap::add(a[i]);
        cout << Treap::kth_max_sum(K) << endl;
        for(int i = 1; i <= leaf_cnt; i++) Treap::erase(a[i]);
    }
}

Compilation message

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

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 12 ms 2644 KB Output is correct
4 Correct 10 ms 2644 KB Output is correct
5 Correct 14 ms 2644 KB Output is correct
6 Correct 4 ms 2644 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct
8 Correct 337 ms 2824 KB Output is correct
9 Correct 189 ms 2852 KB Output is correct
10 Correct 74 ms 2816 KB Output is correct
11 Correct 414 ms 2824 KB Output is correct
12 Correct 127 ms 2788 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 12 ms 2644 KB Output is correct
4 Correct 10 ms 2644 KB Output is correct
5 Correct 14 ms 2644 KB Output is correct
6 Correct 4 ms 2644 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct
8 Correct 337 ms 2824 KB Output is correct
9 Correct 189 ms 2852 KB Output is correct
10 Correct 74 ms 2816 KB Output is correct
11 Correct 414 ms 2824 KB Output is correct
12 Correct 127 ms 2788 KB Output is correct
13 Execution timed out 1086 ms 2936 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 12 ms 2644 KB Output is correct
4 Correct 10 ms 2644 KB Output is correct
5 Correct 14 ms 2644 KB Output is correct
6 Correct 4 ms 2644 KB Output is correct
7 Correct 9 ms 2644 KB Output is correct
8 Correct 337 ms 2824 KB Output is correct
9 Correct 189 ms 2852 KB Output is correct
10 Correct 74 ms 2816 KB Output is correct
11 Correct 414 ms 2824 KB Output is correct
12 Correct 127 ms 2788 KB Output is correct
13 Execution timed out 1086 ms 2936 KB Time limit exceeded
14 Halted 0 ms 0 KB -