There was a problem of timeout in a problem in OJ.

this problem occurs when individuals use BFS. I am puzzled. Please advise
about the results

The

code is as follows:

-sharpinclude<iostream>
-sharpinclude<stdlib.h>
-sharpinclude<stdio.h>
-sharpinclude<vector>
-sharpinclude<queue>
-sharpinclude<algorithm>
-sharpinclude<math.h>
using namespace std;
using std::vector;
using std::queue;
const int maxn=100010;
struct node{
    double data;
    vector<int>child;
    int layer;
}Node[maxn];
int n;
double p,r;

bool cmp(node a,node b){
    return a.layer>b.layer;
}

void BFS(int x){
    int layer=-1;
    queue<int>q;
    q.push(x);
    while(!q.empty()){
        layerPP;
        int length=q.size();
        for(int i=0;i<length;iPP){
            int index=q.front();
            q.pop();
            Node[index].layer=layer;
            for(int j=0;j<Node[index].child.size();jPP){
                q.push(Node[index].child[j]);
            }
        }
    }
}
int main(){
    int root;
    int mem;
    scanf("%d%lf%lf",&n,&p,&r);
    for(int i=0;i<n;iPP){
        scanf("%d",&mem);
        if(mem!=-1){
            //
            Node[mem].child.push_back(i);
        }else{
            root=i;
        }
    }
    BFS(root);
    sort(Node,Node+n,cmp);
    int layer=Node[0].layer;
    int sum=0;
    for(int i=0;i<n;iPP){
        if(Node[i].layer==layer)
            sumPP;
    }
    printf("%.2f %d",p*pow(1+r/100,layer),sum);
    system("pause");
    return 0;
}

-sharpinclude <stdio.h> -sharpinclude <string.h> -sharpinclude <vector> -sharpinclude <queue> -sharpinclude <algorithm> using namespace std; const int maxn = 100000 + 5; vector<int> G[maxn]; int lenth[maxn]; // int bfs(int root) { int maxTran = 0; memset(lenth, -1, sizeof(lenth)); queue<int> Q; Q.push(root); lenth[root] = 0; while(!Q.empty()) { int supp = Q.front(); Q.pop(); for(int i = 0; i < G[supp].size(); iPP) { int buy = G[supp][i]; lenth[buy] = lenth[supp] + 1; Q.push(buy); maxTran = max(maxTran, lenth[buy]); } } return maxTran; } int main() { int n; double p, r; while(scanf("%d %lf %lf", &n, &p, &r) == 3) { for(int i = 0; i < n; iPP) { G[i].clear(); } int supp, root; for(int i = 0; i < n; iPP) { scanf("%d", &supp); if(supp != -1) { G[supp].push_back(i); } else { root = i; } } // int maxTran = bfs(root); double highPrice = p; for(int i = 0; i < maxTran; iPP) { highPrice *= (1 + r / 100); } // price int cnt = 0; for(int i = 0; i < n; iPP) { if(lenth[i] == maxTran) cntPP; } printf("%.2f %d\n", highPrice, cnt); } return 0; }

There was a problem of timeout in a problem in OJ.

ideas

AC Code