| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 786479 |
2023-07-18T08:15:48 Z |
이동현(#10029) |
Paths (RMI21_paths) |
C++17 |
|
290 ms |
42624 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;
struct maxk{
int sz;
multiset<int> st1, st2;
int sum;
maxk(){}
maxk(int n){
sz = n;
sum = 0;
}
void push(int val){
st1.insert(val);
sum += val;
if((int)st1.size() > sz){
st2.insert(*st1.begin());
sum -= *st1.begin();
st1.erase(st1.begin());
}
}
void erase(int val){
if(val < *st1.begin()){
st2.erase(val);
}
else{
st1.erase(val);
sum -= val;
if((int)st1.size() < sz && (int)st2.size()){
sum += *(--st2.end());
st1.insert(*(--st2.end()));
st2.erase(--st2.end());
}
}
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<vector<vector<int>>> way(n);
for(int i = 1; i < n; ++i){
int x, y, z;
cin >> x >> y >> z;
--x, --y;
way[x].push_back({y, z});
way[y].push_back({x, z});
}
auto getdis = [&](auto&&self, int x, int pr, int ndis, vector<int>&vc)->void{
vc[x] = ndis;
for(auto&nxt:way[x]){
if(nxt[0] == pr){
continue;
}
self(self, nxt[0], x, ndis + nxt[1], vc);
}
};
vector<int> imsi(n);
getdis(getdis, 0, -1, 0, imsi);
pair<int, int> mx1 = {-1, -1};
for(int i = 0; i < n; ++i){
mx1 = max(mx1, {imsi[i], i});
}
vector<int> dis1(n), dis2(n);
getdis(getdis, mx1.second, -1, 0, dis1);
pair<int, int> mx2 = {-1, -1};
for(int i = 0; i < n; ++i){
mx2 = max(mx2, {dis1[i], i});
}
getdis(getdis, mx2.second, -1, 0, dis2);
int X = mx1.second, Y = mx2.second;
vector<int> oline(n);
vector<int> line = {X};
oline[X] = 1;
int now = X;
do{
for(auto&nxt:way[now]){
if(dis1[nxt[0]] + dis2[nxt[0]] == dis1[Y] && dis1[now] + nxt[1] == dis1[nxt[0]]){
now = nxt[0];
break;
}
}
line.push_back(now);
oline[now] = 1;
}while(now != Y);
vector<vector<int>> vc(n);
vector<vector<int>> child(n);
vector<int> mx(n);
vector<int> rtdist(n), maxdep(n);
auto dodp = [&](auto&&self, int x, int pr, int rt, int ndis)->void{
child[rt].push_back(x);
rtdist[x] = ndis;
for(auto&nxt:way[x]){
if(nxt[0] == pr || oline[nxt[0]]){
continue;
}
self(self, nxt[0], x, rt, ndis + nxt[1]);
maxdep[x] = max(maxdep[x], nxt[1] + maxdep[nxt[0]]);
mx[nxt[0]] += nxt[1];
if((int)vc[nxt[0]].size() > (int)vc[x].size()){
swap(vc[x], vc[nxt[0]]);
swap(mx[x], mx[nxt[0]]);
}
if(!(int)vc[nxt[0]].size()){
continue;
}
for(auto&i:vc[nxt[0]]){
vc[x].push_back(i);
}
if(mx[x] < mx[nxt[0]]){
vc[x].push_back(mx[x]);
mx[x] = mx[nxt[0]];
}
else{
vc[x].push_back(mx[nxt[0]]);
}
}
if(!(int)vc[x].size()){
vc[x] = {0};
}
};
for(auto&i:line){
dodp(dodp, i, -1, i, 0);
vc[i].push_back(mx[i]);
sort(vc[i].begin(), vc[i].end());
reverse(vc[i].begin(), vc[i].end());
}
vector<int> ans(n);
maxk heap;
auto sol = [&](auto&&self, int x, int pr, int add)->void{
int nans = add + heap.sum + rtdist[x];
ans[x] = max(ans[x], nans);
for(auto&nxt:way[x]){
if(pr == nxt[0] || oline[nxt[0]]){
continue;
}
if(maxdep[nxt[0]] + nxt[1] == maxdep[x]){
heap.erase(maxdep[x]);
heap.push(maxdep[nxt[0]]);
}
self(self, nxt[0], x, add);
if(maxdep[nxt[0]] + nxt[1] == maxdep[x]){
heap.erase(maxdep[nxt[0]]);
heap.push(maxdep[x]);
}
}
};
for(int rep = 0; rep < 2; ++rep){
heap = maxk(k - 1);
int dist = 0, pre = X;
for(auto&i:line){
for(auto&nxt:way[i]){
if(nxt[0] == pre){
dist += nxt[1];
break;
}
}
pre = i;
for(auto&j:vc[i]){
heap.push(j);
}
sol(sol, i, -1, dist);
}
reverse(line.begin(), line.end());
}
if(k >= 2){
heap = maxk(k - 2);
for(auto&i:line){
for(auto&j:vc[i]){
heap.push(j);
}
}
for(auto&i:line){
sol(sol, i, -1, dis1[Y]);
}
}
for(int i = 0; i < n; ++i){
cout << ans[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
290 ms |
42624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
