TLE even after following the tutorial in Question D Educational Round CodeForces round 168 (Div-2) even after following the tutorial
Разница между en1 и en2, 2,706 символ(ов) изменены

~~~~~
I dont know why I am getting TLE in the question . Even after I applied the answer after seeing tutorial .↵
[Question link ](https://codeforces.net/contest/1997/problem/D)↵

[tutorial link](https://codeforces.net/blog/entry/132154)↵

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;↵
}↵


~~~~~↵

История

 
 
 
 
Правки
 
 
  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)