Submission #1306554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306554		mohammadsam	Tourism (JOI23_tourism)	C++20	100 / 100	348 ms	37464 KiB

tourism

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb            push_back
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 1e5 + 10,SQ=320,LOG=20;
const ll inf = 2e9 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n , m,q;
vector<int> g[N];
int sz[N],head[N],par[N],pr[N][LOG],dis[N],st[N],ft[N],ind[N],big[N],tim=1;
set<pii> stk[N];
int arr[N];
int ln[N];
pii seg[N<<2];
vector<pii> quer[N];
int ans[N];
void pre_dfs(int u,int p){
    sz[u] = 1;
    par[u] = p;
    for(auto h : g[u]){
        if(h != p){
            pre_dfs(h,u);
            if(sz[big[u]] < sz[h]) big[u] = h;
            sz[u] += sz[h];
        }
    }
}
void HLD(int u,int p,int hd){
    head[u] = hd;
    st[u] = tim++;
    ind[st[u]] = u;
    dis[u] = dis[p] + 1;
    ln[head[u]]++;
    pr[u][0] = par[u];
    for(int j = 1 ; j < LOG;j++) pr[u][j] = pr[pr[u][j-1]][j-1];
    if(big[u]) HLD(big[u],u,hd);
    for(auto h : g[u]){
        if(h != p && big[u] != h){
            HLD(h,u,h);
        }
    }
    ft[u] = tim;
}
pii merge(const pii& a,const pii& b){
    return {min(a.fi,b.fi),max(a.sec,b.sec)};
}
void build(int u=1,int l=1,int r=m+1){
    if(r-l==1){
        seg[u] = {st[arr[l]],st[arr[l]]};
        return ;
    }
    int mid = (l+r)>>1;
    build(lid,l,mid);
    build(rid,mid,r);
    seg[u] = merge(seg[lid],seg[rid]);
}
pii get(int s,int e,int u=1,int l=1,int r=m+1){
    if(s <= l && r <= e) return seg[u];
    int mid = (l+r)>>1;
    if(e <= mid) return get(s,e,lid,l,mid);
    if(s >= mid) return get(s,e,rid,mid,r);
    return merge(get(s,e,lid,l,mid),get(s,e,rid,mid,r));
}
struct Fenwick{
    int fen[N];
    void add(int i,int v){
        for(i++;i < N;i+=-i&i) fen[i] += v;
    }
    int ask(int i){
        int ans = 0;
        for(i++;i;i-=-i&i) ans += fen[i];
        return ans;
    }
    int get(int s,int e){
        return ask(e-1) - ask(s-1);
    }
} F;
void Upd(int u,int id,int v){
    auto it = stk[u].upper_bound({id,inf});
    int cnt = (*it).fi;
    if(it != stk[u].begin()) cnt -= (*prev(it)).fi;
    F.add((*it).sec,-cnt);
    F.add((*it).sec,(*it).fi - id);
    if(it != stk[u].begin()){
        it--;
        while(true){
            int lst = (it == stk[u].begin() ? 0 : (*prev(it)).fi);
            F.add((*it).sec,-((*it).fi - lst));
            if(it == stk[u].begin()) break;
            it--;
        }
    }
    F.add(v,id);
    stk[u].insert({id,v});
    while((*stk[u].begin()) != Mp(id,v)) stk[u].erase(*stk[u].begin());
}
void update(int u,int i){
    while(u != 0){
        Upd(head[u],dis[u]-dis[head[u]]+1,i);
        u = pr[head[u]][0];
    }
}
int lift(int u,int k){
    for(int j = 0 ; j < LOG;j++){
        if(k&(1<<j)) u = pr[u][j];
    }
    return u;
}
int lca(int u,int v){
    if(dis[u] > dis[v]) swap(u,v);
    v = lift(v,dis[v] - dis[u]);
    if(u==v) return u;
    for(int j = LOG-1;j >= 0;j--){
        if(pr[u][j] != pr[v][j]) u = pr[u][j],v=pr[v][j];
    }
    return pr[u][0];
}

int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    cin >> n >> m >> q;
    for(int i = 0;i < n - 1;i++){
        int u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i =1 ;i <= m;i++) cin >> arr[i];
    pre_dfs(1,0);
    HLD(1,0,1);
    build();
    for(int i= 1 ;i <= q;i++){
        int l,r;
        cin >> l >> r;
        quer[r].pb({l,i});
    }
    for(int i= 1;i <= n;i++){
        if(head[i] == i){
            stk[i].insert({ln[i],0});
            F.add(0,ln[i]);
        }
    }

    // for(int i =1 ;i <= n;i++) cout << head[i] << sep;
    // cout << endl;
    for(int i =1 ;i <= m;i++){
        update(arr[i],i);
        // cout << i << " --- " << endl;
        // for(int j =0;j <= m ;j++) cout << F.get(j,j+1) << sep;
        // cout << endl;
        // for(int j =1 ;j <= n ;j++){
        //     cout << j << " : ";
        //     cout << endl;
        //     for(auto h : stk[j]) cout << h.fi << sep << h.sec << endl;
        // }
        for(auto h : quer[i]){
            int tmp = F.get(h.fi,m+1);
            pii x = get(h.fi,i+1);
            int u = ind[x.fi];
            int v=  ind[x.sec];
            u = lca(u,v);
            ans[h.sec] = tmp - dis[u];
        }
    }
    for(int i = 1;i <= q;i++) cout << ans[i] + 1 << endl;
    return 0;
}

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