Submission #1264547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264547		asemoonabi	LOSTIKS (INOI20_lostiks)	C++20	0 / 100	122 ms	95160 KiB

Main

#include<bits/stdc++.h>
using namespace std ; 
typedef long long ll ;
#define el '\n'
const ll maxn = 2e6 + 100 ;
const ll maxk = 23 ;
ll n , spt[maxn][maxk] , h[maxn] , par[maxn] , Close[maxn] ;
ll st , en ;
vector<pair<ll,ll>> adj[maxn] ;
ll frst[maxn] ;
ll ans = 0 ;
vector<ll> tour ;
void dfs_lca(ll u , ll p){
    par[u] = p ;
    h[u] = (p == -1) ? 0 : h[p]+1 ;
    frst[u] = tour.size() ; 
    tour.push_back(u) ;
    for(auto [v,w] : adj[u]){
        if(v == p){Close[u] = w;continue;}
        dfs_lca(v,u) ;
        tour.push_back(u) ;
    }
    return ;
}
ll get_lca(ll u , ll v){
    ll l = min(frst[u],frst[v]) , r = max(frst[u],frst[v])+1 ;
    ll lg = 31-__builtin_clz(r-l) ;
    if(h[spt[l][lg]] < h[spt[r-(1<<lg)][lg]]){return spt[l][lg];}
    else{return spt[r-(1<<lg)][lg];}
}
void f(ll S , ll E){
    ll LCA = get_lca(S,E) ;
    ll A = S ;
    ll cnt = 0 ;
    ll k = 0 ;
    while(A != LCA){
        if(Close[A] == -1){
            cnt++ ; A = par[A];
        }
        else{
            f(S,Close[A]) ;
            ll x = Close[A] ;
            Close[A] = -1 ;
            f(x,A) ;
            f(A,E) ;
            return ;
        }
    }
    while(A != E){
        ll V = 0 ;
        for(auto [v,w] : adj[A]){
            if(v == par[A]){continue;}
            if(get_lca(v,E) != v){continue;}
            V = v ;
        }
        if(Close[V] == -1){
            cnt++ ;A = V;
        }
        else{
            f(S,Close[V]) ;
            ll x = Close[V] ;
            Close[V] = -1 ;
            f(x,A) ; 
            f(A,E) ;
            return ;
        }
    }
    ans += cnt ;
    return ;
}
void solve(){
    cin>>n ;
    cin>>st>>en ; st-- ; en-- ;
    for(ll i = 0 ; i < n-1 ; i++){
        ll u , v , w ; 
        cin>>u>>v>>w ; u-- ; v-- ; w-- ;
        adj[u].push_back({v,w}) ; adj[v].push_back({u,w}) ;
    }
    dfs_lca(st,-1) ;
    for(ll i = 0 ; i < tour.size() ; i++){
        spt[i][0] = tour[i] ;
    }
    for(ll x = 1 ; x < maxk ; x++){
        for(ll i = 0 ; i < tour.size() ; i++){
            if(tour.size() < i + (1<<x)){break;}
            if(h[spt[i][x-1]] < h[spt[i+(1<<(x-1))][x-1]]){spt[i][x] = spt[i][x-1];}
            else{spt[i][x] = spt[i+(1<<(x-1))][x-1];}
        }
    }
    f(st,en) ;
    cout<<ans<<el ;
    return ;
}
int main(){
    //std::ios_base::sync_with_stdio(false) , cin.tie(nullptr) ;
    solve() ;
}

• Subtask 1: 0 / 23
• Subtask 2: 0 / 36
• Subtask 3: 0 / 41