Submission #1183098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183098		Gray	Tourism (JOI23_tourism)	C++20	28 / 100	5096 ms	111504 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD (ll)(1e9+7)

ll n, m, q;
vector<vector<ll>> A;
vector<ll> tin;
vector<ll> smap;

struct Tree{
    vector<vector<pair<ll, ll>>> st;
    vector<ll> level, eid, log;
    vector<pair<ll, ll>> euler;
    void dfs1(ll u, ll p, ll clev, ll &timer){
        tin[u]=timer; timer++; level[u]=clev;
        euler.push_back({clev, u}); eid[u]=euler.size()-1;
        for (auto v:A[u]){
            if (v==p) continue;
            dfs1(v, u, clev+1, timer);
            euler.push_back({clev, u});
        }
    }

    void genST(){
        ll N = euler.size(); log.resize(N+1);
        for (ll i=2; i<=N; i++) log[i]=log[i/2]+1;
        st.resize(log[N]+1, vector<pair<ll, ll>>(N));
        st[0] = euler;
        for (ll i=1; i<=log[N]; i++){
            for (ll j=0; j<=N-(1<<i); j++){
                st[i][j]=min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
            }
        }
    }
    void init(){
        level.resize(n+1); tin.resize(n+1);
        eid.resize(n+1);
        euler.resize(n+1);
        ll timer=0; dfs1(1, 1, 1, timer);
        genST();
    }

    ll lca(ll u, ll v){
        ll l = eid[u], r = eid[v];
        if (l>r) swap(l, r);
        ll lg = log[r-l+1];
        return min(st[lg][l], st[lg][r-(1<<lg)+1]).ss;
    }

    ll dist(ll u, ll v){
        ll lc = lca(u, v);
        return level[u]+level[v]-level[lc]*2;
    }
} tree;
struct TDist{
    set<pair<ll, ll>> euler;
    vector<ll> cnt; ll dist, l, r;
    TDist(){
        cnt.resize(n+1); dist=0;
        l=-1; r=-1;
    }
    void add(ll u){
        // cout << "added " << u << " -> ";
        cnt[u]++; if (cnt[u]==1){
            if (euler.empty()){
                euler.insert({tin[u], u});
            }else if (euler.size()==1){
                dist+=tree.dist(u, (*euler.begin()).ss);
                euler.insert({tin[u], u});
            }else{
                auto iter = euler.upper_bound({tin[u], u});
                if (iter==euler.end()){
                    iter--; dist-=tree.dist((*euler.begin()).ss, tree.lca((*euler.begin()).ss, (*iter).ss));
                    dist+=tree.level[u]-tree.level[tree.lca(u, (*iter).ss)];
                    dist+=tree.level[(*euler.begin()).ss]-tree.level[tree.lca(u, (*euler.begin()).ss)];
                    euler.insert({tin[u], u});
                }else if (iter==euler.begin()){
                    dist-=tree.dist((*iter).ss, tree.lca((*euler.rbegin()).ss, (*iter).ss));
                    dist+=tree.level[u]-tree.level[tree.lca(u, (*euler.rbegin()).ss)];
                    dist+=tree.level[(*iter).ss]-tree.level[tree.lca(u, (*iter).ss)];
                    euler.insert({tin[u], u});
                }else{
                    auto piter=iter; piter--;
                    dist-=tree.level[(*iter).ss]-tree.level[tree.lca((*iter).ss, (*piter).ss)];
                    dist+=tree.level[(*iter).ss]-tree.level[tree.lca((*iter).ss, u)];
                    dist+=tree.level[u]-tree.level[tree.lca(u, (*piter).ss)];
                    euler.insert({tin[u], u});
                }
            }
        }
        // cout << dist << ln;
    }
    void remove(ll u){
        // cout << "removed " << u << " -> ";
        cnt[u]--; if (cnt[u]==0){
            if (euler.size()==1){
                euler.erase(euler.begin());
            }else if (euler.size()==2){
                dist-=tree.dist((*euler.begin()).ss, (*euler.rbegin()).ss);
                euler.erase({tin[u], u});
            }else{
                auto iter = euler.find({tin[u], u});
                ll pu, nu;
                if (iter==euler.begin()){
                    iter++; pu = (*euler.rbegin()).ss; nu = (*iter).ss;
                }else if ((*iter)==(*euler.rbegin())){
                    iter--; pu = (*iter).ss; nu = (*euler.begin()).ss;
                }else{
                    iter--; pu = (*iter).ss; iter++;
                    iter++; nu = (*iter).ss;
                }
                dist-=tree.level[u]-tree.level[tree.lca(pu, u)];
                dist-=tree.level[nu]-tree.level[tree.lca(u, nu)];
                dist+=tree.level[nu]-tree.level[tree.lca(pu, nu)];
                euler.erase({tin[u], u});
            }
        }
        // cout << dist << ln;
    }
    void shift(ll tl, ll tr){
        if (l==-1 and r==-1){
            l=tl; r=tr;
            for (ll i=l; i<=r; i++) add(smap[i]);
        }else{
            while (l>tl){
                l--; add(smap[l]);
            }
            while (r<tr){
                r++; add(smap[r]);
            }
            while (l<tl){
                remove(smap[l]); l++;
            }
            while (r>tr){
                remove(smap[r]); r--;
            }
        }
    }
};

ll B = 70;

void solve(){
    cin >> n >> m >> q; A.resize(n+1);
    for (ll i=0; i<n-1; i++){
        ll u, v; cin >> u >> v;
        A[u].push_back(v); A[v].push_back(u);
    }
    tree.init();
    smap.resize(m);
    for (ll i=0; i<m; i++) cin >> smap[i];
    vector<pair<ll, ll>> qs(q);
    vector<pair<pair<ll, ll>, ll>> sqs(q);
    vector<ll> res(q);
    for (ll i=0; i<q; i++){
        cin >> qs[i].ff >> qs[i].ss; qs[i].ff--; qs[i].ss--;
        sqs[i] = {qs[i], i};
    }
    sort(sqs.begin(), sqs.end());
    TDist tdist; vector<ll> crng;
    ll spi=0, epi=-1;
    for (ll i=0; i<m; i+=B){
        while (epi+1<q and sqs[epi+1].ff.ff<i+B) epi++;
        while (spi<q and sqs[spi].ff.ff<i) spi++;
        crng.clear(); for (ll j=spi; j<=epi; j++) crng.push_back(sqs[j].ss);
        sort(crng.begin(), crng.end(), [&](ll ind1, ll ind2){ return qs[ind1].ss<qs[ind2].ss; });
        for (auto j:crng){
            tdist.shift(qs[j].ff, qs[j].ss);
            res[j]=tdist.dist;
        }
    }
    for (ll i=0; i<q; i++){
        cout << res[i]+1 << ln;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    for (ll c=1; c<=t; c++) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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