제출 #793746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
793746		vjudge1	Tourism (JOI23_tourism)	C++17	100 / 100	472 ms	33704 KiB

tourism

#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 100100;
const int mod = 1e9 + 7;

using namespace std;

int n;
int m;
int q;
int s[N];
int st[N];
int en[N];
int inv[N];
int tin[N];
int tout[N];
int tim;
int a[N];
int f[N][20];
int res[N];
vector<int> v[N];
vector<pair<int, int>> qu[N];

void dfs(int x, int p)
{
    s[x] = 1;
    f[x][0] = p;
    for (int i = 1; i < 20; i++) {
        f[x][i] = f[f[x][i - 1]][i - 1];
    }
    for (int y: v[x]) {
        if (y == p) {
            continue;
        }
        dfs(y, x);
        s[x] += s[y];
    }
}

bool isp(int x, int y)
{
    return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int lca(int x, int y)
{
    if (isp(x, y)) {
        return x;
    } else if (isp(y, x)) {
        return y;
    }
    for (int i = 19; i >= 0; i--) {
        if (!isp(f[x][i], y)) {
            x = f[x][i];
        }
    }
    return f[x][0];
}

void trace(int x, int p)
{
    tin[x] = ++tim;
    inv[tim] = x;
    if (!st[x]) {
        st[x] = tim;
    }

    int big = -1;
    for (int y: v[x]) {
        if(y == p) {
            continue;
        }
        if (big == -1 || s[y] > s[big]) {
            big = y;
        }
    }
    if (big != -1) {
        st[big] = st[x];
        trace(big, x);
        en[x] = en[big];
    } else {
        en[x] = tin[x];
    }
    for (int y: v[x]) {
        if (y == p || y == big) {
            continue;
        }
        trace(y, x);
    }
    tout[x] = tim;
}

int F[N];

void upd(int x, int y)
{
    x = N - x - 10;
    while (x < N) {
        F[x] += y;
        x += x & -x;
    }
}

int get(int x)
{
    x = N - x - 10;
    int res = 0;
    while (x > 0) {
        res += F[x];
        x -= x & -x;
    }
    return res;
}

int t[4 * N];

void push(int x)
{
    if(t[x] != -1) {
        t[x * 2] = t[x * 2 + 1] = t[x];
        t[x] = -1;
    }
}

void cler(int x, int l, int r)
{
    if (t[x] == -2) {
        return;
    } else if (t[x] != -1) {
        if (t[x] > 0) {
            upd(t[x], - (r - l + 1));
            //cout << "- " << t[x] << ' ' << r - l + 1 << "\n";
        }
        t[x] = -2;
        return;
    }
    push(x);
    int m = (l + r) / 2;
    cler(x * 2, l, m);
    cler(x * 2 + 1, m + 1, r);
}

void upd(int x, int l, int r, int tl, int tr, int g)
{
    if (tl > tr) {
        return;
    } else if(l == tl && r == tr) {
        cler(x, l, r);
        t[x] = g;
        //cout << "+ " << g << " " << r - l + 1 << "\n";
        upd(g, r - l + 1);
        return;
    }
    push(x);
    int m = (l + r) / 2;
    upd(x * 2, l, m, tl, min(m, tr), g);
    upd(x * 2 + 1, m + 1, r, max(m + 1, tl), tr, g);
}

void upd(int x, int y, int g)
{
    //cout << x << " " << y << endl;
    while (true) {
        if (st[x] != st[y]) {
            // st[x], tin[x]
            upd(1, 1, n, st[x], tin[x], g);
            x = f[inv[st[x]]][0];
        } else {
            // tin[y], tin[x]
            upd(1, 1, n, tin[y], tin[x], g);
            break;
        }
    }
}

int main() {
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);

    cin >> n >> m >> q;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for (int i = 1; i <= m; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= q; i++) {
        int l, r;
        cin >> l >> r;
        qu[r].push_back({l, i});
    }

    dfs(1, 1);
    trace(1, 1);

    for (int i = 1; i <= m; i++) {
        if (i > 1) {
            int p = lca(a[i - 1], a[i]);
            upd(a[i - 1], p, i - 1);
            upd(a[i], p, i - 1);
        }
        upd(a[i], a[i], i);
        for (auto p: qu[i]) {
            res[p.se] = get(p.fi);
        }
    }

    for (int i = 1; i <= q; i++) {
        cout << res[i] << "\n";
    }
}

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