lameboredgenie's blog

By lameboredgenie, history, 2 weeks ago, In English

this is my code

include<bits/stdc++.h>

using namespace std;

define ll long long

const int maxSize = 2e5+1; vector<vector>dp(maxSize); int main() { ll n,q; cin>>n>>q; ll i,a[n+1]; for(i=1;i<=n;i++) { cin>>a[i]; } int j; // int elm = (log(n+1)/log(2));

for(i=1;i<=n;i++)
{
    dp[i].resize(n+1);
    dp[i][0] = i;
    dp[i][1] = a[i];
}
for(i=1;i<=(log(n)/log(2));i++)
{
    for(j=1;j<=n;j++)
    {

        dp[j][(1<<i)] = dp[dp[j][(1<<i)/2]][(1<<i)/2];
    }
}

while(q--)
{
    ll node,dist;
    cin>>node>>dist;
    vector<ll>v;
    while(dist)
    {
        ll temp = log(dist)/log(2);
        if((1<<temp)<=dist)
        {
            v.push_back((1<<temp));
            dist = dist-(1<<temp);
        }
        else
        {
            break;
        }
    }
    ll start=node;
    for(auto d:v)
    {

        start = dp[start][d];
    }
    // cout<<endl;
    cout<<start<<endl;
}

}

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

You are using O(n^2) memory.

your vector dp will have atmost n^2 memory, therefore exceeding memory limit and causing runtime error. (2e5 x 2e5 = 4e10 , approx 10 GB memory)