Submission #1064856

#TimeUsernameProblemLanguageResultExecution timeMemory
1064856BoomydayJobs (BOI24_jobs)C++17
43 / 100
2088 ms1048576 KiB
// // Created by adavy on 8/18/2024. // #include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1e9 + 7; #define int ll #define f first #define s second pair<ll,ll> merge(pair<ll,ll> a, pair<ll,ll> b){ return {min(a.f,b.f),a.s-max(a.f,b.f)+b.s}; } struct prs{ set<pair<ll,ll>> ps; void insert(pair<ll,ll> p){ /* cout << "ps: " << endl; for(auto& itm:ps){ cout << itm.f << " " << itm.s << endl; } cout << "p: " << p.f << " " << p.s << endl;*/ while(1){ auto it = ps.lower_bound(p); if (it != ps.end()) { if (it-> f <= p.s){ p = merge(p,*it); ps.erase(it); continue; } } auto it2 = ps.upper_bound(p); if (it2 != ps.begin()){ --it2; if (it2->s >= p.f){ p = merge(p,*it2); ps.erase(it2); continue; } } if (p.f > p.s){ ps.clear(); return; } ps.insert(p); break; } } void subtract(ll x){ ll balance = -x; ll neg = balance; while (!ps.empty() && balance < 0){ balance -= ps.begin()->f; neg = min(neg,balance); balance += ps.begin()->s; ps.erase(ps.begin()); } if (balance >= 0){ this->insert({-neg,balance-neg}); } } }; vector<vector<int>> adj; vector<int> val; vector<prs> sets; vector<int> which; void dfs(int v, int p){ int maxsz = -1, maxch = -1; for(int u:adj[v]){ if (u == p) continue; dfs(u,v); if (sets[u].ps.size() > maxsz){ maxsz = sets[u].ps.size(); maxch = u; } } if (maxsz == -1){ which[v] = v; } else { which[v] = which[maxch]; } for(int u:adj[v]){ if (u==p || u == maxch) continue; for(auto& itm:sets[u].ps){ sets[which[v]].insert(itm); } } if (val[v] > 0){ sets[which[v]].insert({0LL,val[v]}); } else { sets[which[v]].subtract(-val[v]); } // output v, sets[which[v]].ps /* cout << "v: " << v << endl; for(auto& itm:sets[which[v]].ps){ cout << itm.f << " " << itm.s << endl; }*/ } signed main(){ std::ios::sync_with_stdio(false); cin.tie(NULL); int N,s; cin >> N >> s; adj.resize(N+1); val.resize(N+1); sets.resize(N+1); which.resize(N+1,-1); val[0] = 0; for(int i=1;i<=N;++i){ ll x,p; cin >> x >> p; val[i] = x; adj[p].push_back(i); adj[i].push_back(p); } dfs(0,-1); int t = s; for(auto& item:sets[which[0]].ps){ if (t >= item.f){ t -= item.f; t += item.s; } } cout << t-s << endl; }

Compilation message (stderr)

Main.cpp: In function 'void dfs(ll, ll)':
Main.cpp:84:31: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   84 |         if (sets[u].ps.size() > maxsz){
      |             ~~~~~~~~~~~~~~~~~~^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...