| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 687683 |
2023-01-26T20:47:33 Z |
QwertyPi |
Paths (RMI21_paths) |
C++14 |
|
600 ms |
20812 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));
crawl(l); crawl(r);
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:107:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
107 | for(auto& [u, we] : G[v]){
| ^
Main.cpp:107:15: warning: unused structured binding declaration [-Wunused-variable]
107 | for(auto& [u, we] : G[v]){
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1067 ms |
20812 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
