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

topic description

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

.

clipboard.png

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


Let me give you some suggestions
1. No one else knows what the title of your code is, so what do you think?
2. With ac and timeout, it is possible that the program can get the correct result, but it still needs to be optimized.
3. BFS is blind. More iterations will be time-consuming and memory-consuming.


ideas

the meaning of the question is to find the height of a tree, you only need to bfs once.

the time complexity is O (n), and the range of this question n is less than n < = 10 ^ 5. We can pass this question.

your code is really messy, and the train of thought is not clear enough. Please compare my code and see what I can optimize.

you can comment or send a private message if you have any questions.

AC Code

-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;
}
MySQL Query : SELECT * FROM `codeshelper`.`v9_news` WHERE status=99 AND catid='6' ORDER BY rand() LIMIT 5
MySQL Error : Disk full (/tmp/#sql-temptable-64f5-7bdf90-15fe4.MAI); waiting for someone to free some space... (errno: 28 "No space left on device")
MySQL Errno : 1021
Message : Disk full (/tmp/#sql-temptable-64f5-7bdf90-15fe4.MAI); waiting for someone to free some space... (errno: 28 "No space left on device")
Need Help?