| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 786453 |
2023-07-18T07:59:37 Z |
이동현(#10029) |
Paths (RMI21_paths) |
C++17 |
|
600 ms |
524288 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;
priority_queue<int, vector<int>, greater<int>> pq;
int mx2, sum;
maxk(int n){
sz = n;
mx2 = sum = 0;
}
void push(int val){
pq.push(val);
sum += val;
if(pq.size() > sz){
mx2 = max(mx2, pq.top());
sum -= pq.top();
pq.pop();
}
}
};
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());
// cout << "RT " << i << endl;
// for(auto&j:vc[i]) cout << j << ' ';
// cout << endl;
}
vector<int> ans(n);
for(int rep = 0; rep < 2; ++rep){
maxk heap(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;
// cout << i << ' ' << dist << ' ' << heap.sum << endl;
for(auto&j:vc[i]){
heap.push(j);
}
for(auto&j:child[i]){
int nans = dist + heap.sum + rtdist[j];
if(maxdep[j] > heap.mx2){
nans += max(heap.mx2, maxdep[j] - rtdist[j]) - maxdep[j];
}
ans[j] = max(ans[j], nans);
}
}
reverse(line.begin(), line.end());
}
if(k >= 2){
maxk heap(k - 2);
for(auto&i:line){
for(auto&j:vc[i]){
heap.push(j);
}
}
for(auto&i:line){
for(auto&j:child[i]){
int nans = heap.sum + dis1[Y] + rtdist[j];
if(maxdep[j] > heap.mx2){
nans += max(heap.mx2, maxdep[j] - rtdist[j]) - maxdep[j];
}
ans[j] = max(ans[j], nans);
}
}
}
for(int i = 0; i < n; ++i){
cout << ans[i] << '\n';
}
return 0;
}
Compilation message
Main.cpp: In member function 'void maxk::push(long long int)':
Main.cpp:20:22: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
20 | if(pq.size() > sz){
| ~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
33964 KB |
Output is correct |
| 2 |
Execution timed out |
648 ms |
524288 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
