oj.uz

Submission #966440

# Submission time Handle Problem Language Result Execution time Memory
966440 2024-04-19T21:29:18 Z shadow_sami Magic Tree (CEOI19_magictree) C++17
6 / 100
 118 ms 133432 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll,ll> pi;
typedef map<ll,ll> mi;
typedef long double ld;
typedef vector<ld> vd;
typedef vector<vector<ld>> vvd;
typedef pair<ld,ld> pd;
#define ff first
#define ss second
#define srt(a) sort(a.begin(),a.end());
#define fip(k, n) for (ll i = k; i < n; i++)
#define fjp(k, n) for (ll j = k; j < n; j++)
#define fin(k, n) for (ll i = k; i >= n; i--)
#define fjn(k, n) for (ll j = k; j >= n; j--)
#define fp(k, n, m) for (ll k = n; k < m; k++)
#define fn(k, n, m) for (ll k = n; k >= m; k--)
#define ordered_set tree<pi, null_type,less< pi >, rb_tree_tag,tree_order_statistics_node_update>
#define totalOne(n) __builtin_popcount(n)
#define backZero(n) __builtin_ctzll(n)
#define frontZero(n) __builtin_clzll(n)
#define fx(k) for ( auto x : k )
#define test ll t;cin >> t;while (t--)
#define nli "\n"

// ==========================(debug)============================================================================================== //

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _printn(x); cerr << nli;
#else
#define debug(x)
#endif

void _printn(ll x){ cerr<<x<<" "; }
void _printn(int x){ cerr<<x<<" "; }
void _printn(ld x){ cerr<<x<<" "; }
void _printn(double x){ cerr<<x<<" "; }
void _printn(string x){ cerr<<x<<" "; }
void _printn(char x){ cerr<<x<<" "; }
void _printn(bool x){ cerr<<x<<" "; }
template<class T,class V>void _printn(pair<T,V> vv);
template<class T> void _printn(vector<T> vv);
template<class T> void _printn(set<T> vv);
template<class T,class V> void _printn(map<T,V> vv);
template<class T> void _printn(multiset<T> vv);
template<class T,class V>void _printn(pair<T,V> vv){ cerr<<"( ";_printn(vv.ff);cerr<<",";_printn(vv.ss);cerr<<")";}
template<class T> void _printn(vector<T> vv){ cerr<<"[ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"]"; };
template<class T> void _printn(set<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T> void _printn(multiset<T> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };
template<class T,class V> void _printn(map<T,V> vv){ cerr<<"{ "; for(auto xx:vv){ _printn(xx);cerr<<" "; } cerr<<"}"; };

// ==========================(debug)============================================================================================== //

ll n,m,tp,tp2,res,cnt,sum,tptp,ans;
const ll mx = 5e5+5;
const ll mxn = 1e3+5;
const ll mod = 1e9+7;

// ==========================(MOD)=============================================================================================== //

ll mod_add(ll aa,ll bb){ return ((aa%mod)+(bb%mod))%mod; }
ll mod_minus(ll aa,ll bb){ return (((aa%mod)-(bb%mod))+10*mod)%mod; }
ll mod_mul(ll aa,ll bb){ return ((aa%mod)*(bb%mod))%mod; }
ll mod_power(ll aa,ll bb){ aa%=mod; ll empowered = 1; bb%=mod-1; while(bb > 0){ if(bb & 1) empowered = mod_mul(empowered,aa); bb = bb >> 1; aa = mod_mul(aa,aa); } return empowered; }
ll mod_divi(ll aa,ll bb){ aa=mod_mul(aa,mod_power(bb,mod-2)); return aa; }

// ==========================(MOD)=============================================================================================== //

bool f = false;
vi adj[mx];
vi adj2[mx];
ll d[mx];
ll w[mx];
ll sr;
ll id[mx];
ll dp[mxn][mxn];
ll timer = 0;
vi lis;
ll l,r,mid,pt;

ll get(ll x){
    l = 0;
    r = lis.size()-1;
    pt = r+1;
    while(l<=r){
        mid = l + (r-l) / 2;
        if(lis[mid]>=x){
            pt = mid;
            r = mid - 1;
        }else
            l = mid + 1;
    }
    return pt+1;
}

void dfs(ll u,ll par){
    fx(adj[u])
        if(x!=par)
            dfs(x,u);
    fx(adj[u]){
        if(x!=par){
            fjp(1,1001)
                dp[id[u]][j] += dp[id[x]][j];        
        }
    }    
    fjp(2,1001)
        dp[id[u]][j] = max(dp[id[u]][j-1],dp[id[u]][j]);
    fjn(1000,d[u])
        dp[id[u]][j] = max(dp[id[u]][j],dp[id[u]][d[u]]+w[u]);
    fjp(1,1001)
        ans = max(ans,dp[id[u]][j]);
    // debug(u);
    // fjp(1,10)
    //     cerr<<dp[u][j]<<" ";
    // cerr<<nli;
    return;
}

vi dfss(ll u,ll par){
    vi v,v2;
    fx(adj[u]){
        v2 = dfss(x,u);
        fx(v2)
            v.push_back(x);
    }
    if(d[u] < 0 && u!=1)
        return v;
    fx(v)
        adj2[u].push_back(x);
    v.clear();
    v.push_back(u);
    return v;
}

void dfs2(ll u,ll par){
    id[u] = timer;
    timer++;
    fx(adj2[u])
        dfs2(x,u);
    return;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input1.txt", "r", stdin);
    //     freopen("output1.txt", "w", stdout);
    //     freopen("error1.txt", "w", stderr);
    // #endif // ONLINE_JUDGE

        cin>>n>>m>>tp;
        fip(0,n+2){
        	adj[i].clear();
        	d[i] = -1;
        }
        fip(2,n+1){
        	cin>>sr;
        	adj[sr].push_back(i);
        }
        ans = 0;
        set<ll>st;
        fip(0,m){
        	cin>>res>>tp2>>tptp;
        	d[res] = tp2;
        	w[res] = tptp;
            st.insert(d[res]);
        }   
        fx(st)     
            lis.push_back(x);
        fip(1,n+1)
            d[i] = get(d[i]);
        ans = 0;
        fip(0,mxn)
            fjp(0,mxn)
                dp[i][j] = 0;
        dfss(1,-1);
        dfs2(1,-1);
        dfs(1,-1);
        cout<<ans<<nli;
        
    cerr << "Time elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 37208 KB Output is correct
2 Correct 8 ms 37208 KB Output is correct
3 Correct 9 ms 37212 KB Output is correct
4 Correct 8 ms 37220 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 8 ms 37212 KB Output is correct
7 Correct 9 ms 37212 KB Output is correct
8 Correct 8 ms 37212 KB Output is correct
9 Correct 9 ms 37212 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 93384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 37468 KB Output is correct
2 Correct 13 ms 37656 KB Output is correct
3 Correct 14 ms 37668 KB Output is correct
4 Runtime error 118 ms 133432 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 91264 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 37208 KB Output is correct
2 Correct 8 ms 37208 KB Output is correct
3 Correct 9 ms 37212 KB Output is correct
4 Correct 8 ms 37220 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 8 ms 37212 KB Output is correct
7 Correct 9 ms 37212 KB Output is correct
8 Correct 8 ms 37212 KB Output is correct
9 Correct 9 ms 37212 KB Output is correct
10 Runtime error 90 ms 91220 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 76996 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 37208 KB Output is correct
2 Correct 8 ms 37208 KB Output is correct
3 Correct 9 ms 37212 KB Output is correct
4 Correct 8 ms 37220 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 8 ms 37212 KB Output is correct
7 Correct 9 ms 37212 KB Output is correct
8 Correct 8 ms 37212 KB Output is correct
9 Correct 9 ms 37212 KB Output is correct
10 Correct 13 ms 37468 KB Output is correct
11 Correct 13 ms 37656 KB Output is correct
12 Correct 14 ms 37668 KB Output is correct
13 Runtime error 118 ms 133432 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 37208 KB Output is correct
2 Correct 8 ms 37208 KB Output is correct
3 Correct 9 ms 37212 KB Output is correct
4 Correct 8 ms 37220 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 8 ms 37212 KB Output is correct
7 Correct 9 ms 37212 KB Output is correct
8 Correct 8 ms 37212 KB Output is correct
9 Correct 9 ms 37212 KB Output is correct
10 Runtime error 90 ms 93384 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -