제출 #1094629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094629		_8_8_	Tourism (JOI23_tourism)	C++17	18 / 100	197 ms	30040 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]);
        // cout << c[tl] << ' ' << c[tl + 1] << ' ' << x << '\n';
        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 mn[N * 4], mod[N * 4], mx[N * 4];

void make(int v, int val) {
    mod[v] = mx[v] = mn[v] = val;
}
void push(int v) {
    if(mod[v]) {
        make(v + v, mod[v]);
        make(v + v + 1, mod[v]);
        mod[v] = 0;
    }
}
void upd(int l, int r, int val, int v = 1, int tl = 1, int tr = n) {
    if(l > r|| tl > r || l > tr) return;
    if(tl >= l && tr <= r) {
        make(v, val);
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        upd(l, r, val, v + v, tl, tm);
        upd(l, r, val, v + v + 1, tm + 1, tr);
        mx[v] = max(mx[v + v], mx[v + v + 1]);
        mn[v] = min(mn[v + v], mn[v + v + 1]);
    }
}
int find(int val, int v = 1, int tl = 1, int tr = n) { 
    if(mn[v] >= val) {
        return (tr - tl + 1);
    } 
    if(mx[v] < val) {
        return 0;
    }
    push(v);
    int tm = (tl + tr) >> 1;
    return find(val,v + v, tl, tm) + find(val, v + v + 1, tm + 1, tr);
}
void nv(int v, int i) {
    while(v != 1) {
        upd(tin[head[v]], tin[v], i);
        // cout << tin[head[v]] << ' ' << tin[v] << '\n';
        v = up[head[v]][0];
    }
}
int res[N];
void out(int v = 1, int tl = 1, int tr = n) {
    if(tl == tr) {
        // cout << mx[v] << " ";
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        out(v + v, tl, tm);
        out(v + v + 1, tm + 1, tr);
    }
}
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);
    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});
    }
    for(int i = 1; i <= m; i++) {
        nv(c[i], i);
        if(i == 3) {
            // out();
            // cout << find(1) << '\n';
            // return;
        }
        for(auto [l, id]:qr[i]) {
            int x = get(l, i - 1).second;
            // cout << x << '\n';
            res[id] = find(l) - 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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41