Submission #1255420

#TimeUsernameProblemLanguageResultExecution timeMemory
1255420magic_tripMagic Tree (CEOI19_magictree)C++20
100 / 100
101 ms36844 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma optimize("unroll-loops") #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define all(x) x.begin(), x.end() #define rll(x) x.rbegin(), x.rend() #define COMP(x) x.erase(unique(all(x)), x.end()) #define MOD 1000000007 #define MOD2 998244353 #define sz(x) (ll)x.size() typedef __int128_t lll; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll,ll> pll; typedef pair<ll, pll> PP; const ll Lnf = 2e18; ll n, m, k; ll num[101010]; map<ll,ll> mp[101010]; vector<ll> adj[101010]; ll d[101010], w[101010]; void dfs(ll x){ for(auto next : adj[x]){ dfs(next); if(sz(mp[num[next]]) > sz(mp[num[x]]))swap(num[x],num[next]); for(auto [a,b] : mp[num[next]])mp[num[x]][a] += b; } if(d[x]<=k){ mp[num[x]][d[x]] += w[x]; ll s = 0; auto it = mp[num[x]].upper_bound(d[x]); while(it != mp[num[x]].end()){ s += it->second; if(w[x] >= s)it = mp[num[x]].erase(it); else{ it->second = s-w[x]; break; } } } } int main(){ fast; cin>>n>>m>>k; for(int i = 1 ; i <= n ; i++)num[i] = i, d[i]=Lnf; for(int i = 2 ; i <= n ; i++){ ll a; cin>>a; adj[a].push_back(i); } for(int i = 1 ; i <= m ; i++){ ll v; cin>>v>>d[v]>>w[v]; } dfs(1); ll s = 0; for(auto [a,b] : mp[num[1]])s+=b; cout<<s; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...