I dont know why I am getting TLE in the question . Even after I applied the answer after seeing tutorial . Question 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;
}
Auto comment: topic has been updated by VISH9756 (previous revision, new revision, compare).
277259887 works where I have replaced tree representation from
map<int, vector<int>>
tovector<vector<int>>
. I have also replaced your array representation frommap<int,int>
tovector<int>
.Let's look at your code. You have a binary search that runs in O(log(1e9)) . Your checker for change will work in worst cases n * (logn * n); * v(statement) v will be large due to map and also due to recursion n = 2e5
logn = 18
log(1e9) = 30 map which degrades performance. Maybe the problem will be solved if we use dynamic programming that will store answers that have already been given and replace map with vector.
I changed map to vector and also used fast input link
I think you didn't have the FastIO and that's the reason you need to add ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); just after the main() for faster execution