| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 509746 |
2022-01-14T09:16:23 Z |
minhcool |
Paths (RMI21_paths) |
C++17 |
|
259 ms |
65936 KB |
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ordered_set tree<ii, null_type, greater<ii>, rb_tree_tag, tree_order_statistics_node_update>
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 2e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, k;
vector<ii> Adj[N];
int cnt;
int edg[N];
int l[N], r[N], p[N], d[N], rev[N];// rev: reverse of euler tour
int mx[N << 2], pos[N << 2];
int laz[N << 2];
int par[N];
bool vis[N];
void build(int id, int l, int r){
if(l == r){
mx[id] = d[rev[l]];
pos[id] = l;
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
pos[id] = ((mx[id << 1] == mx[id]) ? pos[id << 1] : pos[id << 1 | 1]);
}
void er(int id, int l, int r, int posi){
if(l == r){
mx[id] = -oo;
return;
}
int mid = (l + r) >> 1;
if(mid >= posi) er(id << 1, l, mid, posi);
else er(id << 1 | 1, mid + 1, r, posi);
mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
pos[id] = ((mx[id << 1] == mx[id]) ? pos[id << 1] : pos[id << 1 | 1]);
mx[id] -= laz[id];
}
void upd(int id, int l, int r, int L, int R, int val){
if(l > R || r < L) return;
if(l >= L && r <= R){
laz[id] += val;
mx[id] -= val;
return;
}
int mid = (l + r) >> 1;
upd(id << 1, l, mid, L, R, val);
upd(id << 1 | 1, mid + 1, r, L, R, val);
mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
pos[id] = ((mx[id << 1] == mx[id]) ? pos[id << 1] : pos[id << 1 | 1]);
mx[id] -= laz[id];
}
void dfs(int u, int pa){
cnt++;
l[u] = p[u] = cnt;
for(auto it : Adj[u]){
int v = it.fi, w = it.se;
if(v == pa) continue;
par[v] = u;
d[v] = d[u] + w;
edg[v] = w;
dfs(v, u);
}
r[u] = cnt;
}
int vertex[N];
int IT2[N << 2];
ordered_set os;
void build2(int id, int l, int r){
if(l == r){
IT2[id] = vertex[l];
mx[id] = l;
return;
}
int mid = (l + r) >> 1;
build2(id << 1, l, mid);
build2(id << 1 | 1, mid + 1, r);
IT2[id] = max(IT2[id << 1], IT2[id << 1 | 1]);
mx[id] = (IT2[id << 1] == IT2[id] ? mx[id << 1] : mx[id << 1 | 1]);
}
void upd(int id, int l, int r, int pos, int val){
if(l == r){
IT2[id] += val;
return;
}
int mid = (l + r) >> 1;
if(mid >= pos) upd(id << 1, l, mid, pos, val);
else upd(id << 1 | 1, mid + 1, r, pos, val);
IT2[id] = max(IT2[id << 1], IT2[id << 1 | 1]);
mx[id] = (IT2[id << 1] == IT2[id] ? mx[id << 1] : mx[id << 1 | 1]);
}
ii get(int id, int l, int r, int L, int R){
if(l > R || r < L || l > r) return {-oo, -oo};
if(l >= L && r <= R) return {IT2[id], mx[id]};
int mid = (l + r) >> 1;
return max(get(id << 1, l, mid, L, R), get(id << 1 | 1, mid + 1, r, L, R));
}
int answer[N];
int contain[N];
void dfs_ans(int u, int p){
for(auto it : Adj[u]){
int v = it.fi, w = it.se;
if(v == p) continue;
ii temp1 = get(1, 1, n, l[v], r[v]);
ii temp2 = max(get(1, 1, n, 1, l[v] - 1), get(1, 1, n, r[v] + 1, n));
answer[v] = answer[u];
//cout << v << " " << contain[v] << " " << vertex[contain[v]] << "\n";
os.erase({vertex[contain[v]], contain[v]});
os.insert({vertex[contain[v]] - w, contain[v]});
assert(os.size() == n);
//cout << (*os.find_by_order(k - 1)).fi << "\n";
answer[v] -= max(0LL, vertex[contain[v]] - max(vertex[contain[v]] - w, (*os.find_by_order(k - 1)).fi));
vertex[contain[v]] -= w;
upd(1, 1, n, contain[v], -w);
int temp = (*os.find_by_order(k - 1)).fi;
os.erase({vertex[temp2.se], temp2.se});
os.insert({vertex[temp2.se] + w, temp2.se});
assert(os.size() == n);
answer[v] += max(0LL, (vertex[temp2.se] + w) - max(vertex[temp2.se], temp));
vertex[temp2.se] += w;
upd(1, 1, n, temp2.se, w);
dfs_ans(v, u);
vertex[contain[v]] += w;
os.insert({vertex[contain[v]], contain[v]});
os.erase({vertex[contain[v]] - w, contain[v]});
assert(os.size() == n);
vertex[temp2.se] -= w;
os.insert({vertex[temp2.se], temp2.se});
os.erase({vertex[temp2.se] + w, temp2.se});
assert(os.size() == n);
upd(1, 1, n, contain[v], w);
upd(1, 1, n, temp2.se, -w);
}
}
void process(){
cin >> n >> k;
for(int i = 1; i < n; i++){
int x, y, w;
cin >> x >> y >> w;
Adj[x].pb({y, w});
Adj[y].pb({x, w});
}
dfs(1, 1);
for(int i = 1; i <= n; i++){
rev[p[i]] = i;
}
build(1, 1, n);
for(int i = 1; i <= n; i++){
int mxx = pos[1], temp = mxx;
if(i <= k) answer[1] += mx[1];
vertex[mxx] = mx[1];
er(1, 1, n, mxx);
mxx = rev[mxx];
//white--;
while(mxx && !vis[mxx]){
vis[mxx] = 1;
upd(1, 1, n, l[mxx], r[mxx], edg[mxx]);
contain[mxx] = temp;
mxx = par[mxx];
}
}
for(int i = 1; i <= n; i++) os.insert({vertex[i], i});
build2(1, 1, n);
dfs_ans(1, 1);
for(int i = 1; i <= n; i++) cout << answer[i] << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
process();
}
/*
1 2
1 3
2 4
3 5
2 6
6 7
6 8
*/
Compilation message
In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
from Main.cpp:2:
Main.cpp: In function 'void dfs_ans(long long int, long long int)':
Main.cpp:144:20: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::detail::tree_traits<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
144 | assert(os.size() == n);
| ~~~~~~~~~~^~~~
Main.cpp:152:20: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::detail::tree_traits<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
152 | assert(os.size() == n);
| ~~~~~~~~~~^~~~
Main.cpp:160:20: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::detail::tree_traits<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
160 | assert(os.size() == n);
| ~~~~~~~~~~^~~~
Main.cpp:164:20: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::detail::tree_traits<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::greater<std::pair<long long int, long long int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
164 | assert(os.size() == n);
| ~~~~~~~~~~^~~~
Main.cpp:138:6: warning: variable 'temp1' set but not used [-Wunused-but-set-variable]
138 | ii temp1 = get(1, 1, n, l[v], r[v]);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 7 |
Runtime error |
8 ms |
10316 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 7 |
Runtime error |
8 ms |
10316 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 7 |
Runtime error |
8 ms |
10316 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
259 ms |
65936 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5068 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 4 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 5 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 6 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 7 |
Runtime error |
8 ms |
10316 KB |
Execution killed with signal 6 |
