oj.uz

답안 #1011290

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1011290 2024-06-30T09:34:44 Z 12345678 Jobs (BOI24_jobs) C++17
0 / 100
 421 ms 90704 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], -2e18);
    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){}
      |         ^~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 277 ms 85076 KB Output is correct
2 Correct 421 ms 84476 KB Output is correct
3 Correct 354 ms 83708 KB Output is correct
4 Incorrect 198 ms 90704 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 54364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 54364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 54364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 277 ms 85076 KB Output is correct
2 Correct 421 ms 84476 KB Output is correct
3 Correct 354 ms 83708 KB Output is correct
4 Incorrect 198 ms 90704 KB Output isn't correct
5 Halted 0 ms 0 KB -