| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 537519 |
2022-03-15T07:36:30 Z |
maomao90 |
Paths (RMI21_paths) |
C++17 |
|
107 ms |
10184 KB |
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, int> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 100005
int n, k;
vii adj[MAXN];
multiset<ll> st;
ll mx[MAXN];
void dfs(int u, int p) {
mx[u] = 0;
bool leaf = 1;
for (auto [v, w] : adj[u]) {
if (v == p) continue;
leaf = 0;
dfs(v, u);
auto it = st.find(mx[v]);
st.insert(mx[v] + w);
if (it != st.end()) {
st.erase(st.find(mx[v]));
} else {
st.erase(st.begin());
}
mxto(mx[u], mx[v] + w);
}
if (leaf && st.size() < k) {
st.insert(0);
}
}
ll cur, ans[MAXN];
void reroot(int u, int p) {
pll fmx = MP(0, u), smx = MP(0, u);
for (auto [v, w] : adj[u]) {
if (mx[v] + w >= fmx.FI) {
smx = fmx;
fmx = MP(mx[v] + w, v);
} else if (mx[v] + w > smx.FI) {
smx = MP(mx[v] + w, v);
}
}
ans[u] = cur;
for (auto [v, w] : adj[u]) {
if (v == p) continue;
auto it = st.find(mx[v] + w);
st.insert(mx[v]);
cur += mx[v];
ll er2 = -1;
if (it != st.end()) {
er2 = mx[v] + w;
st.erase(it);
cur -= mx[v] + w;
} else {
er2 = *st.begin();
cur -= *st.begin();
st.erase(st.begin());
}
ll omx = mx[u];
int o = -1;
if (v == fmx.SE) {
mx[u] = smx.FI;
o = smx.SE;
} else {
mx[u] = fmx.FI;
o = fmx.SE;
}
it = st.find(mx[u]);
st.insert(mx[u] + w);
cur += mx[u] + w;
ll er1 = -1;
if (it != st.end()) {
er1 = mx[u];
st.erase(it);
cur -= mx[u];
} else {
er1 = *st.begin();
cur -= *st.begin();
st.erase(st.begin());
}
reroot(v, u);
st.insert(er1);
cur += er1;
st.erase(mx[u] + w);
cur -= mx[u] + w;
mx[u] = omx;
st.insert(er2);
cur += er2;
st.erase(mx[v]);
cur -= mx[v];
}
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> n >> k;
REP (i, 1, n) {
int a, b, c; cin >> a >> b >> c;
adj[a].pb(MP(b, c));
adj[b].pb(MP(a, c));
}
if (k == 1) {
vll dist(n + 1, 0);
vll ans(n + 1, 0);
auto dfs = [&] (auto &&self, int u, int p) {
if (0) return -1;
int mx = u;
for (auto [v, w] : adj[u]) {
if (v == p) continue;
dist[v] = dist[u] + w;
int x = self(self, v, u);
if (dist[mx] < dist[x]) {
mx = x;
}
}
return mx;
};
dist[1] = 0;
int a = dfs(dfs, 1, -1);
dist[a] = 0;
int b = dfs(dfs, a, -1);
REP (i, 1, n + 1) {
mxto(ans[i], dist[i]);
}
dist[b] = 0;
dfs(dfs, b, -1);
REP (i, 1, n + 1) {
mxto(ans[i], dist[i]);
}
REP (i, 1, n + 1) {
cout << ans[i] << '\n';
}
return 0;
}
st.clear();
dfs(1, -1);
cur = 0;
for (ll x : st) {
cur += x;
}
ans[1] = cur;
reroot(1, -1);
REP (i, 1, n + 1) {
cout << ans[i] << '\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:58:27: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
58 | if (leaf && st.size() < k) {
| ~~~~~~~~~~^~~
Main.cpp: In function 'void reroot(int, int)':
Main.cpp:91:13: warning: variable 'o' set but not used [-Wunused-but-set-variable]
91 | int o = -1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
9016 KB |
Output is correct |
| 2 |
Correct |
107 ms |
10184 KB |
Output is correct |
| 3 |
Correct |
56 ms |
8652 KB |
Output is correct |
| 4 |
Correct |
69 ms |
9008 KB |
Output is correct |
| 5 |
Correct |
92 ms |
9864 KB |
Output is correct |
| 6 |
Correct |
74 ms |
9032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
