TLE in Question D Educational Round CodeForces round 168 (Div-2) even after following the tutorial

Правка en2, от VISH9756, 2024-08-20 06:36:29

I dont know why I am getting TLE in the question . Even after I applied the answer after seeing tutorial . Question link

tutorial link

my code:-

#include <iostream>
#include <math.h>
#include <map>
#include <utility>
#include <vector>
#include <set>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <iomanip>
#include <numeric>
#include <bitset>
#include <cstdio>

using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;
typedef bitset<64> bl;
typedef unsigned long long int llu;
typedef priority_queue<ll> pq;

#define rep(i, n) for (ll i = 0; i < n; i++)
#define repr(i, n) for (ll i = n-1; i >=0 ; i--)
#define repe(i, n) for (ll i = 0; i <= n; i++)
#define sortv(v) sort(v.begin(), v.end())
#define O cout <<
#define I cin >>
#define F first
#define S second
#define PB push_back

ll inf=1e9;
map<ll,vl> mptree;
map<ll,ll> mp;

bool dns(ll n,ll val){
    if(mptree[n].size()==0 ){
        if(mp[n]>=val){
            return true;
        }else{
            return false;
        }
    }
    for(auto &i:mptree[n]){
        if(mp[i]<val){
            if( (val+val-mp[i])>inf || !dns(i,(val-mp[i]))){
                return false;
            }
        }else if(mp[i]>=val){
            if(!dns(i,val)){
                return false;
            }
        }
    }
    return true;
}

ll solve()
{
   ll n;
   I n;
   vl arr(n);
   rep(i,n){
    I arr[i];
    mp[i+1]=arr[i];
   }
   rep(i,n-1){
    ll x;
    I x;
    mptree[x].push_back(i+2);
   }
   ll answer=0;
   ll l=0,r=1e9;
    while(l<=r){
        ll mid=l+(r-l)/2;
        if(dns(1,mid)){
            answer=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return answer+arr[0];
}

int main()
{
    // for input output files
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    // Bit manipulation
    // __builtin_clz(x): the number of zeros at the beginning of the bit representation
    // __builtin_ctz(x): the number of zeros at the end of the bit representation
    // __builtin_popcount(x): the number of ones in the bit representation
    // __builtin_parity(x): the parity (even or odd) of the number of ones in the bit representation 

    ll t;
    cin >> t;
    while (t--)
    {
        O solve()<<"\n";
        mp.clear();
        mptree.clear();
    }
    return 0;
}


Теги tle

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский VISH9756 2024-08-20 06:36:29 2706 (published)
en1 Английский VISH9756 2024-08-20 06:27:25 58 Initial revision (saved to drafts)