#13193:


TzuchunChen (陳子濬)

學校 : 國立嘉義高級中學
編號 : 59216
來源 : [49.215.236.123]
最後登入時間 :
2019-05-06 08:46:33
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [220.143.194.73] | 發表日期 : 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 (等於等於)

學校 : 不指定學校
編號 : 59749
來源 : [118.166.82.172]
最後登入時間 :
2024-08-05 20:08:48
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [140.115.202.35] | 發表日期 : 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