# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1011291 |
2024-06-30T09:38:05 Z |
12345678 |
Jobs (BOI24_jobs) |
C++17 |
|
382 ms |
91064 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=3e5+5;
ll n, s, x[nx], pa[nx], vs[nx], in[nx], out[nx], rv[nx], sm[nx], mn[nx], t, profit;
vector<ll> d[nx];
struct segtree
{
struct node
{
ll sm, mn, idx, lz, key;
node(ll key=0, ll sm=0, ll mn=0, ll idx=0, ll lz=0): key(key), sm(sm), mn(mn), idx(idx), lz(lz){}
friend node operator+(const node &a, const node &b) {return (a.key>=b.key)?a:b;}
} d[4*nx];
void updatenode(int i)
{
if (d[i].sm<0) d[i].key=-2e18;
else d[i].key=d[i].mn;
}
void build(int l, int r, int i)
{
if (l==r) return d[i]=node(0, sm[rv[l]], mn[rv[l]], rv[l]), updatenode(i), void();
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=d[2*i]+d[2*i+1];
updatenode(i);
}
void pushlz(int l, int r, int i)
{
d[i].sm+=d[i].lz;
d[i].mn+=d[i].lz;
if (l!=r) d[2*i].lz+=d[i].lz, d[2*i+1].lz+=d[i].lz;
d[i].lz=0;
updatenode(i);
}
void update(int l, int r, int i, int ql, int qr, ll vl)
{
pushlz(l, r, i);
if (qr<l||r<ql) return;
if (ql<=l&&r<=qr) return d[i].lz+=vl, pushlz(l, r, i), void();
int md=(l+r)/2;
update(l, md, 2*i, ql, qr, vl);
update(md+1, r, 2*i+1, ql, qr, vl);
d[i]=d[2*i]+d[2*i+1];
updatenode(i);
}
ll query(int l, int r, int i, int idx)
{
pushlz(l, r, i);
if (l==r) return d[i].sm;
int md=(l+r)/2;
if (idx<=md) return query(l, md, 2*i, idx);
else return query(md+1, r, 2*i+1, idx);
}
void show(int l, int r, int i)
{
pushlz(l, r, i);
cout<<l<<' '<<r<<' '<<d[i].key<<' '<<d[i].sm<<' '<<d[i].mn<<' '<<d[i].idx<<'\n';
if (l==r) return;
int md=(l+r)/2;
show(l, md, 2*i);
show(md+1, r, 2*i+1);
}
} st;
void dfs(int u)
{
in[u]=++t;
rv[t]=u;
for (auto v:d[u]) sm[v]=sm[u]+x[v], mn[v]=min(mn[u], sm[v]), dfs(v);
out[u]=t;
}
void update(int u)
{
ll tmp=st.query(1, n+1, 1, in[u]);
st.update(1, n+1, 1, in[u], in[u], -1e18);
vs[u]=1;
for (auto v:d[u])
{
if (vs[v]) continue;
st.update(1, n+1, 1, in[v], out[v], -tmp);
}
if (!vs[pa[u]]) update(pa[u]);
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>s;
for (int i=1; i<=n; i++) cin>>x[i]>>pa[i], d[pa[i]].push_back(i);
dfs(0);
st.build(1, n+1, 1);
while (s+st.d[1].key>=0)
{
int u=st.d[1].idx;
s+=st.d[1].sm;
profit+=st.d[1].sm;
update(u);
}
cout<<profit;
}
Compilation message
Main.cpp: In constructor 'segtree::node::node(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:16:29: warning: 'segtree::node::key' will be initialized after [-Wreorder]
16 | ll sm, mn, idx, lz, key;
| ^~~
Main.cpp:16:12: warning: 'long long int segtree::node::sm' [-Wreorder]
16 | ll sm, mn, idx, lz, key;
| ^~
Main.cpp:17:9: warning: when initialized here [-Wreorder]
17 | node(ll key=0, ll sm=0, ll mn=0, ll idx=0, ll lz=0): key(key), sm(sm), mn(mn), idx(idx), lz(lz){}
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
300 ms |
85076 KB |
Output is correct |
2 |
Correct |
382 ms |
84600 KB |
Output is correct |
3 |
Correct |
343 ms |
83564 KB |
Output is correct |
4 |
Incorrect |
219 ms |
91064 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
54360 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
54360 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
54360 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
300 ms |
85076 KB |
Output is correct |
2 |
Correct |
382 ms |
84600 KB |
Output is correct |
3 |
Correct |
343 ms |
83564 KB |
Output is correct |
4 |
Incorrect |
219 ms |
91064 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |