Submission #896388

#	Time	Username	Problem	Language	Result	Execution time	Memory
896388		GrindMachine	Tourism (JOI23_tourism)	C++17	100 / 100	1313 ms	64788 KiB

tourism

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/114003?#comment-1015100

answering multiple queries => think about d&c
how to answer all queries passing through mid?

build virtual tree for all nodes a[l..r]
mid is present in all queries, so run a dfs from root = a[mid]

for a given query, a virtual tree edge is chosen if someone in the subtree is present in the query range (because the root is chosen no matter what and if someone in the subtree of the edge is chosen, then the edge has to be traversed in order to go from the root to that node)
for each edge, find the node with the largest position in the [l..mid-1] part and the node with the smallest position in the [mid+1..r] part
define edge as (lx,rx,w):
add w to the ans if ql <= lx or qr >= rx
for a given query, count the sum of w over all edges that satisfy this condition (also add 1 at the end to account for the root node being selected)
can be done efficiently with sweepline + fenwick

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<int> adj1[N];

struct lca_algo {
    // LCA template (for graphs with 1-based indexing)
 
    int LOG = 1;
    vector<int> depth;
    vector<vector<int>> up;
    vector<int> tin, tout;
    int timer = 1;
 
    lca_algo() {
 
    }
 
    lca_algo(int n) {
        lca_init(n);
    }
 
    void lca_init(int n) {
        while ((1 << LOG) < n) LOG++;
        up = vector<vector<int>>(n + 1, vector<int>(LOG, 1));
        depth = vector<int>(n + 1);
        tin = vector<int>(n + 1);
        tout = vector<int>(n + 1);
 
        lca_dfs(1, -1);
    }
 
    void lca_dfs(int node, int par) {
        tin[node] = timer++;
 
        trav(child, adj1[node]) {
            if (child == par) conts;
 
            up[child][0] = node;
            rep1(j, LOG - 1) {
                up[child][j] = up[up[child][j - 1]][j - 1];
            }
 
            depth[child] = depth[node] + 1;
 
            lca_dfs(child, node);
        }
 
        tout[node] = timer-1;
    }
 
    int lift(int u, int k) {
        rep(j, LOG) {
            if (k & (1 << j)) {
                u = up[u][j];
            }
        }
 
        return u;
    }
 
    int query(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int k = depth[u] - depth[v];
        u = lift(u, k);
 
        if (u == v) return u;
 
        rev(j, LOG - 1, 0) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
 
        u = up[u][0];
        return u;
    }
 
    int get_dis(int u, int v) {
        int lca = query(u, v);
        return depth[u] + depth[v] - 2 * depth[lca];
    }
 
    bool is_ances(int u, int v){
        return tin[u] <= tin[v] and tout[u] >= tout[v];
    }
};

template<typename T>
struct fenwick {
    int siz;
    vector<T> tree;

    fenwick() {

    }

    fenwick(int n) {
        siz = n;
        tree = vector<T>(n + 1);
    }

    int lsb(int x) {
        return x & -x;
    }

    void build(vector<T> &a, int n) {
        for (int i = 1; i <= n; ++i) {
            int par = i + lsb(i);
            tree[i] += a[i];

            if (par <= siz) {
                tree[par] += tree[i];
            }
        }
    }

    void pupd(int i, T v) {
        while (i <= siz) {
            tree[i] += v;
            i += lsb(i);
        }
    }

    T sum(int i) {
        T res = 0;

        while (i) {
            res += tree[i];
            i -= lsb(i);
        }

        return res;
    }

    T query(int l, int r) {
        if (l > r) return 0;
        T res = sum(r) - sum(l - 1);
        return res;
    }
};

lca_algo LCA;
vector<int> a(N);
vector<pii> adj2[N];
vector<int> mxl(N), mnr(N);
vector<array<int,3>> edge_contrib;

void dfs1(int u, int p){
    for(auto [v,d] : adj2[u]){
        if(v == p) conts;
        dfs1(v,u);
        amax(mxl[u],mxl[v]);
        amin(mnr[u],mnr[v]);
        edge_contrib.pb({mxl[v],mnr[v],d});
    }
}

vector<int> ans(N);
vector<array<int,3>> here[N];
fenwick<int> fenw(N);

void go(int l, int r, vector<array<int,3>> queries){
    if(l > r) return;

    int mid = (l+r) >> 1;
    vector<array<int,3>> queries_left, queries_right, queries_curr;

    for(auto [ql,qr,id] : queries){
        if(qr < mid){
            queries_left.pb({ql,qr,id});
        }
        else if(ql > mid){
            queries_right.pb({ql,qr,id});
        }
        else{
            queries_curr.pb({ql,qr,id});
        }
    }

    vector<pii> nodes;
    for(int i = l; i <= r; ++i){
        int u = a[i];
        nodes.pb({LCA.tin[u],u});
    }

    sort(all(nodes));
    int siz = sz(nodes);

    rep(i,siz-1){
        int lca = LCA.query(nodes[i].ss,nodes[i+1].ss);
        nodes.pb({LCA.tin[lca],lca});
    }

    sort(all(nodes));
    nodes.resize(unique(all(nodes))-nodes.begin());
    siz = sz(nodes);

    stack<int> stk;
    stk.push(nodes[0].ss);

    rep1(i,siz-1){
        auto [ti,u] = nodes[i];
        while(!LCA.is_ances(stk.top(),u)){
            stk.pop();
        }
        assert(!stk.empty());
        
        int p = stk.top();
        int d = LCA.get_dis(p,u);
        adj2[p].pb({u,d}), adj2[u].pb({p,d});
        stk.push(u);
    }

    for(auto [ti,u] : nodes){
        mxl[u] = 0;
        mnr[u] = r+1;
    }

    for(int i = l; i < mid; ++i){
        int u = a[i];
        amax(mxl[u],i);
    }
    for(int i = mid+1; i <= r; ++i){
        int u = a[i];
        amin(mnr[u],i);
    }

    edge_contrib.clear();
    int root = a[mid];
    dfs1(root,-1);

    for(auto [ql,qr,id] : queries_curr){
        here[ql].pb({qr,id,1});
    }

    for(auto [lx,rx,w] : edge_contrib){
        here[lx].pb({rx,w,2});
    }

    int sum = 0;
    for(auto [lx,rx,w] : edge_contrib){
        if(lx >= l){
            sum += w;
        }
        else{
            fenw.pupd(rx,w);
        }
    }

    for(int ql = l; ql <= mid; ++ql){
        trav(ar,here[ql]){
            if(ar[2] == 1){
                auto [qr,id,t] = ar;
                int res = sum+fenw.query(1,qr)+1;
                ans[id] = res;
            }
            else{
                auto [rx,w,t] = ar;
                sum -= w;
                fenw.pupd(rx,w);
            }
        }
    }

    for(auto [ql,qr,id] : queries_curr){
        here[ql].clear();
    }
    for(auto [lx,rx,w] : edge_contrib){
        here[lx].clear();
    }
    for(auto [ti,u] : nodes){
        adj2[u].clear();
    }
    for(auto [lx,rx,w] : edge_contrib){
        fenw.pupd(rx,-w);
    }

    go(l,mid-1,queries_left);
    go(mid+1,r,queries_right);
}

void solve(int test_case)
{
    int n,m,q; cin >> n >> m >> q;
    rep1(i,n-1){
        int u,v; cin >> u >> v;
        adj1[u].pb(v), adj1[v].pb(u);
    }
    rep1(i,m) cin >> a[i];

    LCA = lca_algo(n);
    vector<array<int,3>> queries;

    rep1(i,q){
        int l,r; cin >> l >> r;
        queries.pb({l,r,i});
    }

    go(1,m,queries);

    rep1(i,q) cout << ans[i] << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    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