Submission #1254379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254379		nanoblob	Jobs (BOI24_jobs)	C++20	0 / 100	217 ms	35104 KiB

Main

#include <bits/stdc++.h>

using namespace std;

// thank you geothermal :goat:
void __deb(int t) {cerr << t;}
void __deb(long t) {cerr << t;}
void __deb(long long t) {cerr << t;}
void __deb(unsigned int t) {cerr << t;}
void __deb(unsigned long t) {cerr << t;}
void __deb(unsigned long long t) {cerr << t;}
void __deb(float t) {cerr << t;}
void __deb(double t) {cerr << t;}
void __deb(long double t) {cerr << t;}
void __deb(char t) {cerr << '\'' << t << '\'';}
void __deb(const char *t) {cerr << '\"' << t << '\"';}
void __deb(const string &t) {cerr << '\"' << t << '\"';}
void __deb(bool t) {cerr << (t ? "true" : "false");}
template<typename T, typename V>
void __deb(const pair<T, V> &x){ cerr << '{'; __deb(x.first); cerr << ", "; __deb(x.second); cerr << '}'; }
template<typename T>
void __deb(const T &x){
    int f = 0; cerr << '{'; 
    for(auto &i: x){ if(f++) cerr << ", "; __deb(i);}
    cerr << "}";
}
void _rdeb(vector<string> &names, int ind){}
template<typename T, typename... V>
void _rdeb(vector<string> &names, int ind, T t, V... v){
    if(ind != 0) cerr << "==============\n";
    cerr << names[ind] << '\n'; __deb(t); cerr << '\n';
    _rdeb(names, ind+1, v...);
}
template<typename... V>
void _deb(string vars, V... v){
    vector<string> names(1); int in{};
    for(char c : vars)
        if(c == ',' && in == 0){
            while(names.back().size() && isspace(names.back().back())) names.back().pop_back();
            names.push_back("");
        }else{
            if(c == '(') in++; if(c == ')') in--;
            if(!isspace(c) || names.back().size()) names.back().push_back(c);
        }
    while(names.back().size() && isspace(names.back().back())) names.back().pop_back();
    _rdeb(names, 0, v...);
}
#ifdef DEBUG
#define deb(x...) {                              \
    cerr << __func__ << ':' << __LINE__ << '\n'; \
    _deb(#x, x);                                 \
    cerr << '\n';                                \
}
#define debsep(x...) {                           \
    cerr << __func__ << ':' << __LINE__ << '\n'; \
    _deb(#x, x);                                 \
    cerr << "****************************\n";    \
}
#else
#define deb(x...)
#define debsep(x...)
#endif

#define ar array
#define ll long long
typedef int uci;
#define int long long
#define F first
#define S second
typedef complex<double> cd;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define irep(i, a, b) for(int i = a; i > (b); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
#define ve vector
typedef ve<int> vi;
typedef ve<vi> vvi;

seed_seq seq{
    (uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
    (uint64_t) __builtin_ia32_rdtsc(),
    (uint64_t) (uintptr_t) make_unique<char>().get()
};
mt19937 rng(seq);
// mt19937_64 lrng(seq);

struct debugger{
    template <typename T>
    debugger& operator<<(T &a){
        #ifdef DEBUG
            cerr << a;
        #endif
        return *this;
    }
    template <typename T>
    debugger& operator<<(T &&a){
        #ifdef DEBUG
            cerr << a;
        #endif
        return *this;
    }
} deb;

const double PI = acos(-1.0);
const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

//! function insert

//THINK FIRST, CODE SECOND
//DON'T GET STUCK ON ONE STRATEGY
//CALM DOWNNN FOR ONCE IN YOUR LIFE
//REDUCE
//COUGH E??!?!?!! O.O
//uwu i see you ryan

void update(int v, int val, int l, int r, int p, vi &seg){
    if(l > r || p > r || p < l)
        return;
    else if(l == r && l == p)
        seg[v] = val;
    else{
        if(l == r)
            return;
        int mid = l + (r-l)/2;
        update(v*2, val, l, mid, p, seg);
        update(v*2+1, val, mid+1, r, p, seg);
        seg[v] = max(seg[v*2], seg[v*2+1]);
    }
}

int query(int v, int l, int r, int lq, int rq, vi &seg){
    if(l > r || lq > r || rq < l)
        return -LINF;
    else if(lq <= l && r <= rq)
        return seg[v];
    else{
        int mid = l + (r-l)/2;
        return max(query(v*2, l, mid, lq, rq, seg), query(v*2+1, mid+1, r, lq, rq, seg));
    }
}

void solve() {
    int n, s;
    cin >> n >> s;

    vvi adj(n);
    vi ws(n);
    vi ins(n);
    rep(i, 0, n){
        int x, p;
        cin >> x >> p;
        ws[i] = x;
        if(p != 0){
            ins[i]++;
            adj[p-1].push_back(i);
        }
    }

    int out{};

    vi discovered(n);

    vi seg(4*(n+1), -LINF);

    update(1, 0, 0, n, 0, seg);
    vi added(n, -1);
    priority_queue<ar<int, 2>> q;
    for(int i{}; i < n; ++i){
        if(ins[i] == 0){
            q.push({ws[i], i});
            added[i] = 0;
        }
    }
    for(int i = 1; i <= n; ++i){
        auto [w, j] = q.top();
        q.pop();

        int amt = query(1, 0, n, added[j], i-1, seg);

        if(amt+w >= 0)
            update(1, amt+w, 0, n, i, seg);

        for(int k : adj[j]){
            added[k] = i;
            q.push({ws[k], k});
        }
    }


    cout << query(1, 0, n, 0, n, seg) << '\n';
}

uci main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

        // cout << "Case #" << t  << ": ";
        solve();
}

/*
    random number generator stuff
    num = rng(); gives integer number
    num = uniform_int_distribution<int>(a, b)(rng); -> bounds [a, b]
    num = uniform_real_distribution<double>(a, b)(rng); -> bounds [a, b)
    can also instantiate distributions and call on generator:
    uniform_int_distribution<int> thing(a, b);
    num = thing(rng);
*/
// struct custom_hash {
//     static uint64_t splitmix64(uint64_t x) {
//         // http://xorshift.di.unimi.it/splitmix64.c
//         x += 0x9e3779b97f4a7c15;
//         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
//         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
//         return x ^ (x >> 31);
//     }
//     size_t operator()(uint64_t x) const {
//         static const uint64_t FIXED_RANDOM = lrng();
//         return splitmix64(x + FIXED_RANDOM);
//     }
// };

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31