Submission #725917

#	Time	Username	Problem	Language	Result	Execution time	Memory
725917		MohammadAghil	Worst Reporter 4 (JOI21_worst_reporter4)	C++17	79 / 100	339 ms	106776 KiB

worst_reporter2

#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)size(x)
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pp;

void dbg(){
     cerr << endl;
}
template<typename H, typename... T> void dbg(H h, T... t){
     cerr << h << ", ";
     dbg(t...);
}

void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          // freopen("inp.txt", "r", stdin);
          // freopen("out.txt", "w", stdout);
          #define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)
     #else
          #define er(...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll mod = 1e9 + 7, mod2 = 1e9 + 9, maxn = 2e5 + 5, lg = 21, inf = ll(1e9) + 5;

ll pw(ll a, ll b){
     if(b == 0) return 1;
     ll k = pw(a, b>>1);
     return k*k*(b&1ll?a:1);  
}

vector<int> adj[maxn];
ll par[maxn], H[maxn], C[maxn], nxt[maxn];

map<ll, ll> mp[maxn];

void dfs(int r){
     for(int c: adj[r]){
          dfs(c);
          if(sz(mp[c]) > sz(mp[r])) mp[r].swap(mp[c]);
          for(auto&x: mp[c]) mp[r][x.ff] += x.ss;
     }
     mp[r][H[r]] += C[r];
     ll cr = C[r];
     while(cr){
          auto it = mp[r].upper_bound(H[r]);
          if(it == end(mp[r])) return;
          ll mn = min(cr, it->ss);
          cr -= mn, it->ss -= mn;
          if(it->ss == 0) mp[r].erase(it->ff);
     }
}

int main(){ IOS();  
     int n; cin >> n;
     ll sum = 0;
     rep(i,0,n){
          cin >> nxt[i] >> H[i] >> C[i];
          nxt[i]--;
          H[i] = -H[i];
          sum += C[i];
          if(i) adj[nxt[i]].pb(i);
     }
     dfs(0);
     for(auto&c: mp[0]) sum -= c.ss;
     cout << sum << '\n';
     return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 65 / 65
• Subtask 3: 0 / 21