Submission #986276

#	Time	Username	Problem	Language	Result	Execution time	Memory
986276		AlperenT_	Tourism (JOI23_tourism)	C++17	100 / 100	569 ms	47864 KiB

tourism

#include <bits/stdc++.h>
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i , a , b) for(int i=a;i >= b;i--)
using namespace std ;
const int maxn = 1e5 + 10  , N = 1e5 +1 , lg = 20 , maxq = 202   , inf = 1e9  , maxk = 2022  , mod =998244353;
int n , q , m ;
vector <pii> qr[maxn] ;
vector <int> G[maxn] ;
int sb[maxn] , st[maxn] , c[maxn] , en[maxn] , par[maxn] ;
int ms[maxn][lg+1] , me[maxn][lg+1] , dis[maxn] , h[maxn] ;

int lca(int v ,int u){
    if(st[v] <= st[u] && en[u] <= en[v])return v ;
    if(st[u] <= st[v] && en[v] <= en[u])return u ;
    if(dis[h[v]] > dis[h[u]])return lca(par[h[v]] , u) ;
    return lca(v , par[h[u]]) ;
}

int lc(int l ,int r){
    int x = 31 - __builtin_clz(r-l+1); 
    int v = (st[ms[l][x]] < st[ms[r-(1<<x)+1][x]] ? ms[l][x] : ms[r-(1<<x)+1][x]) ;
    int u = (en[me[l][x]] > en[me[r-(1<<x)+1][x]] ? me[l][x] : me[r-(1<<x)+1][x]) ;
    return lca(v , u) ;
}
void b1(int v , int p =0){
    sb[v]=1;
    for(int u : G[v]){
        if(u == p)continue ;
        par[u] = v ;
        dis[u] = dis[v]+1 ;
        b1(u , v) ;
        sb[v] += sb[u] ;
    }
}
int id =1 ; 
void b2(int v , int p =0){
    vector <pii> vec;
    st[v] = id ;id++;
    for(int u : G[v]){
        if(u == p)continue ;
        vec.pb({sb[u] , u});
    }
    sort(all(vec));
    reverse(all(vec));
    rep(i , 0 , sz(vec)-1){
        int u = vec[i].S; 
        if(i == 0){
            h[u] = h[v] ;
            b2(u , v);
        }else{
            h[u] = u ;
            b2(u , v);
        }
    }
    en[v] = id-1 ;
}

int fen[maxn] , ans[maxn] , f[maxn] ;
set <pii> s ;
void fupd(int x, int w){
    x++;
    while(x <= m+1){
        fen[x] += w;
        x += x&-x ;
    }
}
int fque(int x){
    x++;
    int ans = 0;
    while(x){
        ans += fen[x];
        x-=x&-x;
    }
    return ans; 
}
vector <pii> vec;

void find(int v){
    vec.pb({st[h[v]] , st[v]});
    if(h[v]==1)return ;
    find(par[h[v]]) ;
}
void add(int l ,int r){
    s.insert({l,r});
    fupd(f[l] , r-l+1);
}
void rem(int l , int r){
    s.erase({l,r}); 
    fupd(f[l] , -(r-l+1)) ;
}

void fix(int l , int r ,int x){
    auto a = s.lower_bound((pii){l+1, -1}) ; a-- ;
    if((*a).S >= r){
        int L = (*a).F , R = (*a).S ; 
        rem(L,R);
        if(r!=R){
            f[r+1] = f[L] ;
            add(r+1 ,R);
        }
        if(l!=L){
            add(L , l-1);
        
        }
        f[l] = x ;
        add(l,r);
        return ;
    }
    vector <pii>  o ;
    while(a!=s.end()){
        int R = (*a).S ;
        o.pb({(*a).F , R}) ;
        if(R >= r)break ;
        a++;
    }
    for(auto [l,r] : o)rem(l,r) ;
    if(o[0].F != l){
        add(o[0].F , l-1);
    }
    if(o.back().S != r){
        f[r+1] = f[o.back().F];
        add(r+1 , o.back().S) ; 
    }
    f[l] = x ;
    add(l ,r) ;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);   
    cin >> n >> m >> q ;
    rep(i , 1, n-1){
        int v, u ;
        cin >> v >> u ;
        G[v].pb(u);
        G[u].pb(v);
    }
    b1(1);
    h[1] =1 ;
    b2(1);
    rep(i ,1 , m){
        cin >> c[i] ;
        ms[i][0] = me[i][0] = c[i];
    }
    rep(j , 1 , lg){
        rep(i , 1, m){
            int f = (1<<(j-1)) ;
            if(i+f > m){
                me[i][j] = me[i][j-1] ;
                ms[i][j] = ms[i][j-1] ;
            }else{
                ms[i][j] = (st[ms[i][j-1]] < st[ms[i+f][j-1]] ? ms[i][j-1] : ms[i+f][j-1]) ;
                me[i][j] = (en[me[i][j-1]] > en[me[i+f][j-1]] ? me[i][j-1] : me[i+f][j-1]) ;
            }
        }
    }
    rep(i ,1 ,q){
        int l , r; 
        cin >> l >> r ;
        qr[r].pb({l , i});
        ans[i] -= dis[lc(l , r)] ;
    }
    f[1] = 0 ;
    add(1 ,n);
    rep(i , 1, m){
        vec.clear();
        find(c[i]) ;
        for(pii a : vec){
            fix(a.F ,a.S , i);
        }
        for(auto [l,j] : qr[i]){
            ans[j] += fque(i) - fque(l-1) ;
        }
    }
    rep(i ,1 ,q){
        cout << ans[i] << "\n"; 
    }

}
/*
8 8 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 6 4 3 5 2 4 7
3 5
4 6
6 8
1 4
2 3
6 8
5 5
2 8
1 2

*/

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41