| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 626549 |
2022-08-11T14:21:41 Z |
tamthegod |
Paths (RMI21_paths) |
C++14 |
|
217 ms |
72464 KB |
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, k;
vector<pair<int, int>> adj[maxN];
int f[maxN], dp[maxN];
void ReadInput()
{
cin >> n >> k;
for(int i=1; i<n; i++)
{
int u, v, w;
cin >> u >> v >> w;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
}
void predfs(int u, int par)
{
for(auto a : adj[u])
{
int v = a.fi, w = a.se;
if(v == par) continue;
predfs(v, u);
f[u] = max(f[u], f[v] + w);
}
}
void predfs1(int u, int par)
{
vector<pair<int, int>> vc;
for(auto a : adj[u])
{
int v = a.fi, w = a.se;
if(v == par) continue;
vc.pb({f[v] + w, v});
}
sort(vc.begin(), vc.end(), greater<pair<int, int>>());
for(auto a : adj[u])
{
int v = a.fi, w = a.se;
if(v == par) continue;
if(v != vc[0].se) dp[v] = max(dp[u] + w, vc[0].fi + w);
else dp[v] = max(dp[u] + w, vc[1].fi + w);
predfs1(v, u);
}
}
multiset<int, greater<int>> s, s1;
void dfs(int u, int par, int root)
{
int _max = 0, id = 0;
for(auto a : adj[u])
{
int v = a.fi, w = a.se;
if(v == par) continue;
dfs(v, u, root);
if(f[v] + w > _max)
{
_max = f[v] + w;
id = v;
}
}
// cout << u << " " << _max << "\n";
for(auto a : adj[u])
{
int v = a.fi, w = a.se;
if(v == par || v == id) continue;
s.insert(f[v] + w);
}
if(u == root) s.insert(f[u]);
}
int res[maxN], sum = 0;
void add(int val)
{
auto it = s.end();
it--;
if(*it < val)
{
sum -= *it;
sum += val;
s1.insert(*it);
s.erase(it);
s.insert(val);
}
else s1.insert(val);
}
void del(int val)
{
if(s.find(val) != s.end())
{
sum -= val;
s.erase(s.find(val));
if(s1.empty()) return;
sum += *s1.begin();
s.insert(*s1.begin());
s1.erase(s1.begin());
}
else s1.erase(s1.find(val));
}
void reroot(int u, int par)
{
res[u] = sum;
for(auto a : adj[u])
{
int v = a.fi, w = a.se;
if(v == par) continue;
add(f[v]);
add(dp[v]);
del(f[v] + w);
del(dp[v] - w);
reroot(v, u);
add(f[v] + w);
add(dp[v] - w);
del(dp[v]);
del(f[v]);
}
}
void Solve()
{
predfs(2, 0);
predfs1(2, 0);
dfs(2, 0, 2);
for(int v : s) sum += v;
while(s.size() > k)
{
auto it = s.end();
it--;
sum -= *it;
s1.insert(*it);
s.erase(it);
}
reroot(2, 0);
for(int i=1; i<=n; i++) cout << res[i] << '\n';
}
int32_t main()
{
// freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
Solve();
}
Compilation message
Main.cpp: In function 'void Solve()':
Main.cpp:134:20: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
134 | while(s.size() > k)
| ~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
48084 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
48084 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
48084 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
48084 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
34744 KB |
Output is correct |
| 2 |
Runtime error |
159 ms |
72464 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
48084 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
