Submission #1197441

#TimeUsernameProblemLanguageResultExecution timeMemory
1197441joyboy23tiMagic Tree (CEOI19_magictree)C++20
11 / 100
57 ms16576 KiB
#include <bits/stdc++.h> #define fi first #define se second #define FOR(i,l,r) for (int i = l; i <= r; i++) #define FORD(i,l,r) for (int i = l; i >= r; i--) #define el cout <<"\n" #define SZ(x) ((int)(x).size()) #define ALL(x) (x).begin(), (x).end() #define MASK(i) ((1LL)<<(i)) #define BIT(x,i) (((x)>>(i))&(1LL)) #define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int,int> vii; typedef unsigned long long ull; typedef vector<vector<int>> vvi; int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; } const int N=1e5+5; const int base=311; const int mod=1e9+7; const long long INF=1e18+7; const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1}; const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1}; template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;}; template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;}; void add(int &x, int y) { x += y; if (x>=mod) x-=mod;} void sub(int &x, int y) { x -= y; if (x<0) x+=mod;} int mul(int x, int y) {return 1LL * x * y % mod;} int calPw(int x, int y) { int ans = 1; while(y) { if (y&1) ans = 1LL * ans * x % mod; x = 1LL * x * x % mod; y >>= 1; } return ans; } ///KhengmepfromLTVHSFTG int n,m,k,par[N]; pair<int,int>a[N]; vector<int>V,dsk[N]; struct AryaMikhailovnaKujou{ ll st[4*N]; void update(int u,ll val,int id=1,int l=1,int r=100005){ if(l>u||r<u) return; if(l==r){ st[id]=max(st[id],val); return; } int mid=l+r>>1; update(u,val,id*2,l,mid); update(u,val,id*2+1,mid+1,r); st[id]=max(st[id*2],st[id*2+1]); } ll Get(int u,int v,int id=1,int l=1,int r=100005){ if(l>v||r<u) return 0; if(l>=u&&r<=v){ return st[id]; } int mid=l+r>>1; return max(Get(u,v,id*2,l,mid),Get(u,v,id*2+1,mid+1,r)); } }it; void dfs(int u){ for(int v:dsk[u]){ dfs(v); if(a[v].fi!=0){ ll val=it.Get(1,a[v].fi); val+=a[v].se; it.update(a[v].fi,val); } } } void khengmep() { dfs(1); cout<<it.Get(1,k); } void ip() { cin>>n>>m>>k; for(int i=2;i<=n;i++){ cin>>par[i]; dsk[par[i]].push_back(i); } for(int i=1;i<=m;i++){ int v,d,w; cin>>v>>d>>w; a[v]={d,w}; V.push_back(d); } sort(ALL(V)); V.erase(unique(ALL(V)),V.end()); k=0; for(int i=1;i<=n;i++){ if(a[i].fi==0) continue; a[i].fi=lower_bound(ALL(V),a[i].fi)-V.begin()+1; k=max(a[i].fi,k); } } int main() { // freopen("test.inp","r",stdin); // freopen("test.out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(0); int t=1; //cin>>t; while(t--) { ip(); khengmep(); } return 0; }
#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...