Submission #1272054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272054		tvgk	Tourism (JOI23_tourism)	C++20	100 / 100	497 ms	26788 KiB

tourism

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 1e5 + 7;

int n, m, q, mx[mxN], h[mxN], ans[mxN], in[mxN], par[mxN], root[mxN], num, mn[mxN * 4], tree[mxN * 4], beat[mxN * 4], cur, a[mxN];
vector<int> w[mxN];
vector<ii> query[mxN];

void DFS(int j, int tmp)
{
    mx[j] = h[j] = tmp;

    for (int i : w[j])
    {
        if (mx[i])
            continue;

        DFS(i, tmp + 1);
        mx[j] = max(mx[j], mx[i]);
    }
}

bool cmp(int u, int v)
{
    return mx[u] > mx[v];
}

void TiTo(int j)
{
    in[j] = ++num;
    if (!cur)
        cur = j;
    root[j] = cur;

    sort(w[j].begin(), w[j].end(), cmp);
    for (int i : w[j])
    {
        if (in[i])
            continue;

        par[i] = j;
        TiTo(i);
    }
    cur = 0;
}

int LCA(int u, int v)
{
    if (!u || !v)
        return max(u, v);

    while (1)
    {
        if (in[u] > in[v])
            swap(u, v);

        if (root[u] == root[v])
            return u;

        v = par[root[v]];
    }
}

void Build(int j = 1, int l = 1, int r = m)
{
    if (l == r)
    {
        mn[j] = a[l];
        return;
    }

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
    mn[j] = LCA(mn[j * 2], mn[j * 2 + 1]);
}

int Get(int u, int v, int j = 1, int l = 1, int r = m)
{
    if (u > r || l > v)
        return 0;

    if (u <= l && r <= v)
        return mn[j];

    int mid = (l + r) / 2;
    return LCA(Get(u, v, j * 2, l, mid), Get(u, v, j * 2 + 1, mid + 1, r));
}

void Upd_Seg(int vt, int val, int j = 1, int l = 1, int r = m)
{
    if (vt > r || l > vt)
        return;

    tree[j] += val;
    if (l == r)
        return;

    int mid = (l + r) / 2;
    Upd_Seg(vt, val, j * 2, l, mid);
    Upd_Seg(vt, val, j * 2 + 1, mid + 1, r);
}

int Get_Seg(int vt, int j = 1, int l = 1, int r = m)
{
    if (vt < l)
        return 0;

    if (r <= vt)
        return tree[j];

    int mid = (l + r) / 2;
    return Get_Seg(vt, j * 2, l, mid) + Get_Seg(vt, j * 2 + 1, mid + 1, r);
}

void Down(int j)
{
    if (beat[j] == -1)
        return;

    beat[j * 2] = beat[j * 2 + 1] = beat[j];
}

void Upd_Beat(int u, int v, int nw, int j = 1, int l = 1, int r = n)
{
    if (u > r || l > v)
        return;

    if (u <= l && r <= v && beat[j] != -1)
    {
        Upd_Seg(beat[j], -(r - l + 1));
        beat[j] = nw;
        return;
    }
    Down(j);

    int mid = (l + r) / 2;
    Upd_Beat(u, v, nw, j * 2, l, mid);
    Upd_Beat(u, v, nw, j * 2 + 1, mid + 1, r);

    if (beat[j * 2] == beat[j * 2 + 1])
        beat[j] = beat[j * 2];
    else
        beat[j] = -1;
}

void Upd(int j, int cs)
{
    Upd_Seg(cs, h[j]);
    while (j)
    {
        Upd_Beat(in[root[j]], in[j], cs);
        j = par[root[j]];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        w[u].push_back(v);
        w[v].push_back(u);
    }
    DFS(1, 1);
    TiTo(1);

    for (int i = 1; i <= m; i++)
        cin >> a[i];
    Build();

    for (int i = 1; i <= q; i++)
    {
        int u, v;
        cin >> u >> v;
        query[u].push_back({v, i});
    }

    for (int i = m; i >= 1; i--)
    {
        Upd(a[i], i);

        for (ii j : query[i])
            ans[j.se] = Get_Seg(j.fi) - h[Get(i, j.fi)] + 1;
    }

    for (int i = 1; i <= q; i++)
        cout << ans[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