Submission #1271660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271660		tvgk	Tourism (JOI23_tourism)	C++20	10 / 100	136 ms	15944 KiB

tourism

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

int in[mxN], n, l[mxN], r[mxN], sp[mxN * 2][20], h[mxN], a[mxN], num, m, q, ans[mxN];
vector<int> query[mxN], w[mxN];
multiset<ii> s;

void DFS(int j)
{
    in[j] = ++num;
    sp[num][0] = h[j];

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

        h[i] = h[j] + 1;
        DFS(i);
        sp[++num][0] = h[j];
    }
}

int Block(int j)
{
    return j / nB;
}

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

    u = in[u];
    v = in[v];
    if (u > v)
        swap(u, v);
    int dif = __lg(v - u + 1);
    
    return min(sp[u][dif], sp[v - (1 << dif) + 1][dif]);
}

void Add(int& sum, int j)
{
    ii v = *(s.upper_bound({in[j], j}));
    ii u = *(--s.upper_bound({in[j], j}));
    s.insert({in[j], j});

    sum += h[j] + LCA(u.se, v.se);
    sum -= LCA(j, u.se) + LCA(j, v.se);
}

bool cmp(int u, int v)
{
    return r[u] < r[v];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //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);

    for (int i = num; i >= 1; i--)
    {
        for (int j = 1; j <= 18; j++)
            sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
    }

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

    for (int i = 1; i <= q; i++)
    {
        cin >> l[i] >> r[i];

        if (Block(l[i]) == Block(r[i]))
        {
            s.clear();
            s.insert({2 * n, 0});
            s.insert({0, 0});
            for (int j = l[i]; j <= r[i]; j++)
                Add(ans[i], a[j]);

            ii u = *(++s.begin());
            ii v = *(----s.end());
            ans[i] -= LCA(u.se, v.se);
        }
        else
            query[Block(l[i])].push_back(i);
    }

    for (int i = 0; i <= Block(n); i++)
    {
        int sum = 0, v = (i + 1) * nB;
        s.clear();
        s.insert({2 * n, 0});
        s.insert({0, 0});

        sort(query[i].begin(), query[i].end(), cmp);
        for (int j : query[i])
        {
            while (v <= r[j])
            {
                Add(sum, a[v]);
                v++;
            }

            ans[j] = sum;
            for (int u = (i + 1) * nB - 1; u >= l[j]; u--)
                Add(ans[j], a[u]);

            ii u = *(++s.begin());
            ii v = *(----s.end());
            ans[j] -= LCA(u.se, v.se);

            for (int u = (i + 1) * nB - 1; u >= l[j]; u--)
                s.erase(s.find({in[a[u]], a[u]}));
        }
    }

    for (int i = 1; i <= q; i++)
        cout << ans[i] + 1 << '\n';
}

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