| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 687689 |
2023-01-26T21:11:43 Z |
QwertyPi |
Paths (RMI21_paths) |
C++14 |
|
600 ms |
18664 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;
}
};
namespace Segtree{
int t[MAXN << 2], a[MAXN];
int cmp(int q1, int q2){
if(q1 == -1 || q2 == -1) return q1 == -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 -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;
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});
}
dfs(1);
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(1);
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: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:131:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
131 | for(auto& [u, we] : G[v]){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2644 KB |
Output is correct |
| # |
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 |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2644 KB |
Output is correct |
| # |
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 |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 8 |
Correct |
7 ms |
2772 KB |
Output is correct |
| 9 |
Correct |
7 ms |
2868 KB |
Output is correct |
| 10 |
Correct |
6 ms |
2772 KB |
Output is correct |
| 11 |
Correct |
6 ms |
2772 KB |
Output is correct |
| 12 |
Correct |
6 ms |
2772 KB |
Output is correct |
| # |
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 |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 8 |
Correct |
7 ms |
2772 KB |
Output is correct |
| 9 |
Correct |
7 ms |
2868 KB |
Output is correct |
| 10 |
Correct |
6 ms |
2772 KB |
Output is correct |
| 11 |
Correct |
6 ms |
2772 KB |
Output is correct |
| 12 |
Correct |
6 ms |
2772 KB |
Output is correct |
| 13 |
Correct |
13 ms |
3028 KB |
Output is correct |
| 14 |
Correct |
11 ms |
3028 KB |
Output is correct |
| 15 |
Correct |
10 ms |
2960 KB |
Output is correct |
| 16 |
Incorrect |
12 ms |
3024 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
741 ms |
18664 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
2 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 8 |
Correct |
7 ms |
2772 KB |
Output is correct |
| 9 |
Correct |
7 ms |
2868 KB |
Output is correct |
| 10 |
Correct |
6 ms |
2772 KB |
Output is correct |
| 11 |
Correct |
6 ms |
2772 KB |
Output is correct |
| 12 |
Correct |
6 ms |
2772 KB |
Output is correct |
| 13 |
Correct |
13 ms |
3028 KB |
Output is correct |
| 14 |
Correct |
11 ms |
3028 KB |
Output is correct |
| 15 |
Correct |
10 ms |
2960 KB |
Output is correct |
| 16 |
Incorrect |
12 ms |
3024 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
