| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 627976 |
2022-08-13T02:04:52 Z |
Do_you_copy |
Paths (RMI21_paths) |
C++17 |
|
214 ms |
17328 KB |
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 1;
int n, k;
multiset <ll, greater <ll>> S, Save;
//Save: stores edges which are deleted
vector <pii> adj[maxN];
ll dp[maxN];
int pos[maxN], pos2[maxN], max2[maxN];
ll ans[maxN];
void dfs0(int u, int p){
for (auto i: adj[u]){
if (i.fi == p) continue;
dfs0(i.fi, u);
if (dp[u] < dp[i.fi] + i.se){
max2[u] = dp[u];
pos2[u] = pos[u];
dp[u] = dp[i.fi] + i.se;
pos[u] = i.fi;
}
else if (max2[u] < dp[i.fi] + i.se){
max2[u] = dp[i.fi] + i.se;
pos2[u] = i.fi;
}
}
for (auto i: adj[u]){
//if (u == 4) cerr << i.fi << " ";
if (i.fi == p || i.fi == pos[u]) continue;
S.insert(dp[i.fi] + i.se);
//if (u == 4)
//cerr << i.fi << " ?";
//cerr << u << " " << dp[i.fi] + i.se << "?\n";
}
if (u == p) S.insert(dp[u]);
}
ll sum = 0;
void add(ll x){
if (S.size() < k){
S.insert(x);
sum += x;
return;
}
auto it = S.end();
--it;
if (*it < x){
sum -= *it;
sum += x;
Save.insert(*it);
S.insert(x);
S.erase(it);
}
else Save.insert(x);
}
void del(ll x){
auto it = S.find(x);
if (it != S.end()){
sum -= x;
S.erase(it);
if (Save.empty()) return;
auto it1 = Save.begin();
sum += *it1;
S.insert(*it1);
Save.erase(it1);
}
else{
it = Save.find(x);
if (it != Save.end()) Save.erase(it);
}
}
void dfs(int u, int p, int d){
ans[u] = sum;
for (auto i: adj[u]){
if (i.fi == p) continue;
ans[i.fi] = ans[u];
ll maxx = 0;
if (i.fi == pos[u]){
if (pos2[u]) maxx = max(d, max2[u]);
}
else maxx = max(d, dp[u]);
maxx += i.se;
add(maxx);
del(maxx - i.se);
add(dp[i.fi]);
del(dp[i.fi] + i.se);
dfs(i.fi, u, maxx);
del(maxx);
add(maxx - i.se);
del(dp[i.fi]);
add(dp[i.fi] + i.se);
}
}
void Init(){
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});
}
dfs0(1, 1);
for (auto i: S) ans[1] += i;
while (S.size() > k){
auto it = S.end(); --it;
ans[1] -= *it;
Save.insert(*it);
S.erase(it);
}
sum = ans[1];
dfs(1, 1, 0);
for (int i = 1; i <= n; ++i){
cout << ans[i] << "\n";
}
}
#define debu
#define taskname "test"
signed main(){
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
#ifdef debug
freopen(taskname".out", "w", stdout);
#endif
}
faster;
ll tt = 1;
//cin >> tt;
while (tt--){
Init();
}
if (fopen("timeout.txt", "r")){
ofstream timeout("timeout.txt");
timeout << 1000 * double(clock()) / CLOCKS_PER_SEC;
#ifndef debug
cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n";
#endif
}
}
Compilation message
Main.cpp: In function 'void add(ll)':
Main.cpp:66:18: 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]
66 | if (S.size() < k){
| ~~~~~~~~~^~~
Main.cpp: In function 'void Init()':
Main.cpp:133:21: 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]
133 | while (S.size() > k){
| ~~~~~~~~~^~~
Main.cpp: In function 'int main()':
Main.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
214 ms |
17328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
