Submission #1094713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094713		_8_8_	Tourism (JOI23_tourism)	C++17	100 / 100	715 ms	34644 KiB

tourism

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 1e5 + 12, MOD = (int)1e9 + 7;

const int L = 19;
vector<int> g[N];
int n, m, q, c[N], tin[N], tout[N], timer, s[N], head[N], ver[N];
int up[N][19], dep[N];
void bb(int v, int pr = -1) {
    s[v] = 1;
    for(int i = 0; i < (int)g[v].size(); i++) {
        int to = g[v][i];
        if(to == pr) continue;
        bb(to, v);
        s[v] += s[to];
        if(s[to] > s[g[v][0]] || g[v][0] == pr) {
            swap(g[v][i], g[v][0]);
        }
    }
}
void hld(int v, int pr = -1) {
    tin[v] = ++timer;
    ver[timer] = v;
    for(int to:g[v]) {
        if(to == pr) continue;
        if(to == g[v][0]) {
            head[to] = head[v];
        } else {
            head[to] = to;
        }
        hld(to, v);
    }
    tout[v] = timer;
}
vector<pair<int,int>> qr[N];

void dfs(int v, int pr = 1) {
    up[v][0] = pr;
    for(int i = 1; i < L; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int to:g[v]) {
        if(to != pr) {
            dep[to] = dep[v] + 1;
            dfs(to, v);
        }
    }
}
bool is(int v, int u) {
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int lca(int v, int u) {
    if(is(v, u)) return v;
    if(is(u, v)) return u;
    for(int i = L - 1; i >= 0; i--) {
        if(!is(up[v][i], u)) {
            v = up[v][i];
        }
    }
    return up[v][0];
}
pair<int, int> t[N * 4];
void build(int v = 1, int tl = 1, int tr = m - 1) {
    if(tl == tr) {
        int x = lca(c[tl], c[tl + 1]);
        t[v] = {dep[x], x};
    } else {
        int tm = (tl + tr) >> 1;
        build(v + v, tl, tm);
        build(v + v + 1, tm + 1, tr);
        t[v] = min(t[v + v], t[v + v + 1]);
    }
}
const int inf = 1e9;
pair<int, int> get(int l, int r, int v = 1, int tl = 1, int tr = m - 1) {
    if(l > r || tl > r || l > tr) return {inf, inf};
    if(tl >= l && tr <= r) return t[v];
    int tm = (tl + tr) >> 1;
    return min(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}

int T[N * 4];

void upd(int pos, int val) {
    if(!pos) return;
    while(pos <= m) {
        T[pos] += val;
        pos += pos & -pos;
    }
}
int get1(int i) {
    int ret = 0;
    while(i) {
        ret += T[i];
        i -= i & -i;
    }
    return ret;
}
int get2(int l, int r) {
    return get1(r) - get1(l - 1);
}
set<array<int, 3>> st;
void add(int l, int r, int i) {
    auto del = [&](int l, int r, int i) -> void{
        if(i) upd(i, - (r - l + 1));
        st.erase({l, r, i});
    };
    auto ad = [&](int l, int r, int i) -> void{
        upd(i, (r - l + 1));
        st.insert({l, r, i});
    };
    // cout << l << ' ' << r << ' ' << i << '\n';
    while(true) {
        auto it = st.upper_bound({l, (int)1e9, (int)1e9});
        if(it == st.end() || (*it)[0] > r) break;
        if((*it)[1] > r) {
            ad(r + 1, (*it)[1], (*it)[2]);
            del((*it)[0], (*it)[1], (*it)[2]);  
            break;
        } 
        del((*it)[0], (*it)[1], (*it)[2]);  
    }
    auto it = st.upper_bound({l, (int)1e9, (int)1e9});
    if(it != st.begin()) {
        it--;
        if((*it)[1] >= l && (*it)[0] <= l) {
            if((*it)[0] < l) {
                ad((*it)[0], l - 1, (*it)[2]);
            }
            if((*it)[1] > r) {
                ad(r + 1, (*it)[1], (*it)[2]);
            }
            del((*it)[0], (*it)[1], (*it)[2]);  
        }
    }
    st.insert({l , r, i});
    upd(i, r - l + 1);
    // for(auto [_l, _r, k]:st) {
    //     cout << _l << ' ' << _r << ' ' << k << "x\n";
    // }
    // cout << '\n';
}
void nv(int v, int i) {
    do {
        add(tin[head[v]], tin[v], i);
        v = up[head[v]][0];
    }while(v > 1);
    add(1, 1, i);
}
int res[N];
void test() {
    cin >> n >> m >> q;
    for(int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i = 1; i <= m; i++) {
        cin >> c[i];
    }
    dep[1] = 1;
    bb(1);
    head[1] = 1;
    hld(1);
    dfs(1);
    if(m != 1)build();
    for(int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        if(l == r) {
            res[i] = 1;
            continue;
        }
        qr[r].push_back({l, i});
    }
    st.insert({1, n, 0});
    for(int i = 1; i <= m; i++) {
        nv(c[i], i);
        for(auto [l, id]:qr[i]) {
            int x = get(l, i - 1).second;
            res[id] = get2(l, i) - dep[x] + 1;
        }
    }
    for(int i = 1; i <= q; i++) {
        cout << res[i] << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    
    int t = 1; 
    // cin >> t;
    
    while(t--) 
        test();
    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