| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 786572 |
2023-07-18T09:23:38 Z |
이동현(#10029) |
Paths (RMI21_paths) |
C++17 |
|
600 ms |
13572 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int NS = (int)1e5 + 4;
int sz;
multiset<long long> st1, st2;
vector<pair<int, int>> way[NS];
long long imsi[NS], dis1[NS], dis2[NS];
int oline[NS];
int line[NS], lineN;
long long sum;
vector<long long> vc[NS];
vector<int> child[NS];
long long mx[NS], rtdist[NS], maxdep[NS], ans[NS];
void push(long long val){
if(!val) return;
st1.insert(val);
sum += val;
if((int)st1.size() > sz){
st2.insert(*st1.begin());
sum -= *st1.begin();
st1.erase(st1.begin());
}
}
void erase(long long val){
if(!val) return;
if(!sz || val < *st1.begin()){
st2.erase(st2.find(val));
return;
}
st1.erase(st1.find(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;
if(n == 1){
cout << "0\n";
return 0;
}
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, long long ndis, int tp)->void{
if(!tp) imsi[x] = ndis;
else if(tp == 1) dis1[x] = ndis;
else dis2[x] = ndis;
for(auto&nxt:way[x]){
if(nxt.first == pr){
continue;
}
self(self, nxt.first, x, ndis + nxt.second, tp);
}
};
getdis(getdis, 0, -1, 0, 0);
pair<long long, int> mx1 = {-1, -1};
for(int i = 0; i < n; ++i){
mx1 = max(mx1, {imsi[i], i});
}
getdis(getdis, mx1.second, -1, 0, 1);
pair<long long, int> mx2 = {-1, -1};
for(int i = 0; i < n; ++i){
mx2 = max(mx2, {dis1[i], i});
}
if(mx1.second == mx2.second){
mx2 = {-1, (mx1.second + 1) % n};
}
getdis(getdis, mx2.second, -1, 0, 2);
int X = mx1.second, Y = mx2.second;
if(X == Y) while(true){}
line[lineN++] = X;
oline[X] = 1;
int now = X;
do{
for(auto&nxt:way[now]){
if(dis1[nxt.first] + dis2[nxt.first] == dis1[Y] && dis1[now] + nxt.second == dis1[nxt.first]){
now = nxt.first;
break;
}
}
line[lineN++] = now;
oline[now] = 1;
}while(now != Y);
auto dodp = [&](auto&&self, int x, int pr, int rt, long long ndis)->void{
child[rt].push_back(x);
rtdist[x] = ndis;
for(auto&nxt:way[x]){
if(nxt.first == pr || oline[nxt.first]){
continue;
}
self(self, nxt.first, x, rt, ndis + nxt.second);
maxdep[x] = max(maxdep[x], nxt.second + maxdep[nxt.first]);
mx[nxt.first] += nxt.second;
if((int)vc[nxt.first].size() > (int)vc[x].size()){
swap(vc[x], vc[nxt.first]);
swap(mx[x], mx[nxt.first]);
}
if(!(int)vc[nxt.first].size()){
continue;
}
for(auto&i:vc[nxt.first]){
vc[x].push_back(i);
}
if(mx[x] < mx[nxt.first]){
vc[x].push_back(mx[x]);
mx[x] = mx[nxt.first];
}
else{
vc[x].push_back(mx[nxt.first]);
}
}
if(!(int)vc[x].size()){
vc[x] = {0};
}
};
for(int ii = 0; ii < lineN; ++ii){
continue;
int i = line[ii];
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());
while((int)vc[i].size() && vc[i].back() == 0){
vc[i].pop_back();
}
}
auto sol = [&](auto&&self, int x, int pr, long long add)->void{
ans[x] = max(ans[x], add + sum + rtdist[x]);
for(auto&nxt:way[x]){
if(pr == nxt.first || oline[nxt.first]){
continue;
}
erase(maxdep[nxt.first] + nxt.second);
push(maxdep[nxt.first]);
self(self, nxt.first, x, add);
erase(maxdep[nxt.first]);
push(maxdep[nxt.first] + nxt.second);
}
};
for(int rep = 0; rep < 2; ++rep){
sz = k - 1, sum = 0;
st1.clear(), st2.clear();
long long dist = 0;
int pre = X;
for(int ii = 0; ii < lineN; ++ii){
int i = line[ii];
for(auto&nxt:way[i]){
if(nxt.first == pre){
dist += nxt.second;
break;
}
}
pre = i;
for(auto&j:vc[i]){
push(j);
// cout << j << ' ';
}
// cout << endl;
sol(sol, i, -1, dist);
}
reverse(line, line + lineN);
}
if(k >= 2){
sz = k - 2, sum = 0;
st1.clear(), st2.clear();
for(int ii = 0; ii < lineN; ++ii){
int i = line[ii];
for(auto&j:vc[i]){
push(j);
}
}
for(int ii = 0; ii < lineN; ++ii){
int i = line[ii];
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 |
Execution timed out |
1077 ms |
7380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
7380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
7380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
7380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1056 ms |
13572 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1077 ms |
7380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
