TLE!!!OrzOrz%%%快来大佬呀!!
查看原帖
TLE!!!OrzOrz%%%快来大佬呀!!
1397174
zldx楼主2024/10/3 17:25

哪个好心的大佬

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>v;
vector<vector<int>>ve;
vector<int> h;
int n,m,s;
void C(){
    cin>>n>>m>>s;
    v=vector<vector<int>>(n+1);
    h=vector<int>(n+1);
    ve=vector<vector<int>>(n+1,vector<int>(21,0));
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
}
void f(int x,int father){
    ve[x][0]=father;
    for(int i=1;i<20;i++){
        ve[x][i]=ve[ve[x][i-1]][i-1];
    }
    for(auto i:v[x]){
        if(i!=father){
            h[i]=h[x]+1;
            f(i,x);
        }
    }
}
void LCA(int a,int b){
    if(h[a]!=h[b]){
        if(h[a]<h[b])swap(a,b);
        for(int i=20;i>=0;i--){
            if(h[ve[a][i]]>=h[b]){
                a=ve[a][i];
            }
        }
    }
    if(a==b){
        cout<<a<<endl;
        return;
    }

    for(int i=20;i>=0;i--){
        if(ve[a][i]!=ve[b][i]){
            a=ve[a][i];
            b=ve[b][i];
        }
    }
    cout<<ve[a][0]<<endl;
}
void detect(){
    for(int i=1;i<=n;i++){
        cout<<i<<":   ";
        for(int j=0;j<20;j++){
            cout<<ve[i][j]<<" ";
        }
        cout<<endl;
    }
    for(int i=1;i<=n;i++){
        cout<<h[i]<<" ";
    }
    cout<<endl;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    C();
    h[s]=1;
    f(s,0);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        LCA(a,b);
    }
//    detect();
}

同步一关对了一个,还有三个TLE

2024/10/3 17:25
加载中...