#13193: TLE


TzuchunChen (陳子濬)

School : 國立嘉義高級中學
ID : 59216
IP address : [49.215.236.123]
Last Login :
2019-05-06 08:46:33
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [220.143.194.73] | Post Date : 2017-12-31 19:48

幫忙修改,一直TLE

#include <bits/stdc++.h>
using namespace std;
int parent[100005],high[100005];
void find_high(int n){
    while(parent[n]){
        if(high[parent[n]]>=high[n]+1)
            return;
        high[parent[n]]=high[n]+1;
        n=parent[n];
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,k,son;
    while(cin>>n){
        memset(high,0,sizeof(high));
        memset(parent,0,sizeof(parent));
        for(int i=1;i<=n;i++){
            cin>>k;
                for(int j=0;j<k;j++){
                    cin>>son;
                    parent[son]=i;
                }
        }
        for(int i=1;i<=n;i++)
            if(!parent[i]){
                cout<<i<<'\n';
                break;
            }
        for(int i=1;i<=n;i++)
            find_high(i);
        int sum=0;
        for(int i=1;i<=n;i++)
          sum+=high[i];
        cout<<sum<<'\n';
        }
    return 0;
}

 
#13194: Re:TLE


sdf6ry6j (等於等於)

School : No School
ID : 59749
IP address : [118.166.81.182]
Last Login :
2022-09-16 11:27:21
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [140.115.202.35] | Post Date : 2017-12-31 21:08

幫忙修改,一直TLE

#include <bits/stdc++.h>
using namespace std;
int parent[100005],high[100005];
void find_high(int n){
    while(parent[n]){
        if(high[parent[n]]>=high[n]+1)
            return;
        high[parent[n]]=high[n]+1;
        n=parent[n];
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,k,son;
    while(cin>>n){
        memset(high,0,sizeof(high));
        memset(parent,0,sizeof(parent));
        for(int i=1;i<=n;i++){
            cin>>k;
                for(int j=0;j<k;j++){
                    cin>>son;
                    parent[son]=i;
                }
        }
        for(int i=1;i<=n;i++)
            if(!parent[i]){
                cout<<i<<'\n';
                break;
            }
        for(int i=1;i<=n;i++)
            find_high(i);
        int sum=0;
        for(int i=1;i<=n;i++)
          sum+=high[i];
        cout<<sum<<'\n';
        }
    return 0;
}


當圖為一條鍊時你的算法為O(n^2)

 
ZeroJudge Forum