| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 769510 |
2023-06-29T17:07:15 Z |
vjudge1 |
Paths (RMI21_paths) |
C++17 |
|
246 ms |
15712 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define pb push_back
#define ss second
#define ff first
#define all(x) (x).begin(), (x).end()
const int nax = 1e5 + 4;
int n, k, sz = 1;
vector<pii> adj[nax];
vector<pll> st;
vector<ll> lazy;
ll d[nax];
int dpar[nax];
int par[nax], vis[nax], eul[nax], endeul[nax], cor[nax];
int cureul = -1;
void dfs(int x, ll curd, int p)
{
par[x] = p;
d[x] = curd;
dpar[x] = curd - d[p];
vis[x] = 0;
eul[x] = ++cureul;
cor[cureul] = x;
for(auto e: adj[x])
{
if(e.ff == p)
continue;
dfs(e.ff, curd + e.ss, x);
}
endeul[x] = cureul;
}
void build(int p, int l, int r)
{
if(l == r)
{
st[p] = {d[cor[l]], cor[l]};
return ;
}
build(2 * p, l, (l + r)/2);
build(2 * p + 1, (l + r)/2 + 1, r);
st[p] = max(st[2 * p], st[2 * p + 1]);
lazy[p] = 0ll;
}
void propagate(int p, int l, int r)
{
if(lazy[p])
{
if(l != r)
{
lazy[2 * p] += lazy[p];
lazy[2 * p + 1] += lazy[p];
}
st[p].ff += lazy[p];
lazy[p] = 0ll;
}
}
void update(int p, int l, int r, int i, int j, ll val)
{
propagate(p, l, r);
if(i > j)
return ;
if(l >= i && r <= j)
{
lazy[p] += val;
propagate(p, l, r);
return ;
}
int m = (l + r)/2;
update(2 * p, l, m, i, min(j, m), val);
update(2 * p + 1, m + 1, r, max(i, m + 1), j, val);
pll a ={st[2 * p].ff + lazy[2 * p], st[2 * p].ss} ;
pll b ={st[2 * p + 1].ff + lazy[2 * p + 1], st[2 * p + 1].ss};
st[p] = max(a,b);
return ;
}
pll query(int p, int l, int r, int i, int j)
{
propagate(p, l, r);
if(i > j)
return {0ll, 0ll};
if(l >= i && r <= j)
return st[p];
int m = (l + r)/2;
return max(query(2 * p, l, m, i, min(j, m)),
query(2 * p + 1, m + 1, r, max(i, m + 1), j));
}
void solve()
{
cin >> n >> k;
for(int i= 1; i < n; i++)
{
int a, b;
cin >> a >> b;
ll c; cin >> c;
adj[a].pb({b, c});
adj[b].pb({a, c});
}
dfs(1, 0, 0);
while(sz < n)
sz = (sz << 1);
lazy.assign(2 * sz + 1, 0);
st.assign(2 * sz + 1, {0, 0});
build(1, 0, sz - 1);
for(int root = 1; root <= n; root++)
{
if(k > 1)
{
cureul = -1;
dfs(root, 0, 0);
build(1, 0, sz - 1);
vis[root] = 1;
ll ans = 0ll;
for(int i = 1;i <= k; i++)
{
propagate(1, 0, sz - 1);
pll o = st[1];
if(o.ff == 0)
break;
int cur = o.ss;
ans += o.ff;
while(!vis[cur])
{
update(1, 0, sz - 1, eul[cur], endeul[cur], -dpar[cur]);
vis[cur] = 1;
cur= par[cur];
}
}
cout << ans << '\n';
}
else
{
update(1, 0, sz - 1, eul[root], endeul[root], -d[root]);
update(1, 0, sz - 1, 0, eul[root] - 1, d[root]);
update(1, 0, sz - 1, endeul[root] + 1, n - 1, d[root]);
propagate(1, 0, sz - 1);
pll o = st[1];
update(1, 0, sz - 1, eul[root], endeul[root], d[root]);
update(1, 0, sz - 1, 0, eul[root] - 1, -d[root]);
update(1, 0, sz - 1, endeul[root] + 1, n - 1, -d[root]);
}
}
}
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tt = 1;
while(tt--)
solve();
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:145:17: warning: variable 'o' set but not used [-Wunused-but-set-variable]
145 | pll o = st[1];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
246 ms |
15712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
