Submission #1220872

#TimeUsernameProblemLanguageResultExecution timeMemory
1220872TrumlingMagic Tree (CEOI19_magictree)C++20
11 / 100
49 ms10052 KiB
//Trumling ©
//Αφόδευε υψηλά και ηγνάντει 
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()

vector<vector<ll>>g;
vector<pair<ll,ll>>f;
ll k;
ll seg[400000];
void update(int l,int r,int idx,int p,ll u)
{
    if(l>p || r<p)
        return ;

    if(l==r)
    {
        seg[idx]=u;
        return ;
    }
    update(l,(l+r)/2,idx*2,p,u);
    update((l+r)/2+1,r,idx*2+1,p,u);
    seg[idx]=max(seg[idx*2],seg[idx*2+1]);
}

ll query(int l,int r,int idx,int L,int R)
{
    if(l>R || r<L)
        return 0;

    if(L<=l && r<=R)
        return seg[idx];
    
    return max(query(l,(l+r)/2,idx*2,L,R),query((l+r)/2+1,r,idx*2+1,L,R));
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n,m;
cin>>n>>m>>k;
g.assign(n+1,vector<ll>());
f.assign(n+1,{0,0});


for(int i=2;i<=n;i++)
{
    ll x;
    cin>>x;
    g[i].pb(x);
    g[x].pb(i);
}

for(int i=0;i<m;i++)
    {
        ll x,y,z;
        cin>>x>>y>>z;
        f[x]={y,z};
    }

for(int i=n;i>=1;i--)
    if(f[i].F!=0)
    {
        ll q=query(1,k,1,1,f[i].F);
       // cout<<f[i].F<<','<<q<<' ';
        update(1,k,1,f[i].F,q+1);
    }
        

cout<<seg[1];
        
}

#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...