Submission #796326

#	Time	Username	Problem	Language	Result	Execution time	Memory
796326		Johann	Tourism (JOI23_tourism)	C++14	28 / 100	5076 ms	28296 KiB

tourism

#include "bits/stdc++.h"
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

int N, M, Q;
vi C;
vector<set<int>> CC;
vvi adj;
vi in, out;
vi depth;
vvi vorg;

void dfs(int v, int p, int &idx)
{
    in[v] = idx++;
    depth[v] = depth[p] + 1;
    vorg[v][0] = p;
    for (int i = 1; i < sz(vorg[v]); ++i)
        vorg[v][i] = vorg[vorg[v][i - 1]][i - 1];

    for (int u : adj[v])
        if (u != p)
            dfs(u, v, idx);

    out[v] = idx++;
}

bool is_vorg(int a, int b)
{
    return in[a] <= in[b] && out[b] <= out[a];
}

int lca(int a, int b)
{
    if (is_vorg(a, b))
        return a;
    if (is_vorg(b, a))
        return b;

    int tmp;
    for (int j = sz(vorg[a]) - 1; j >= 0; --j)
    {
        tmp = vorg[a][j];
        if (!is_vorg(tmp, b))
            a = tmp;
    }
    return vorg[a][0];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M >> Q;

    adj.resize(N);
    for (int i = 0, a, b; i < N - 1; ++i)
    {
        cin >> a >> b;
        --a, --b;
        adj[a].push_back(b), adj[b].push_back(a);
    }
    int idx = 0;
    in.resize(N), out.resize(N), depth.assign(N, -1);
    vorg.assign(N, vi(ceil(log2(N) + 1)));
    dfs(0, 0, idx);

    C.resize(M), CC.resize(N);
    for (int i = 0; i < M; ++i)
    {
        cin >> C[i];
        --C[i];
        CC[C[i]].insert(i);
    }

    for (int i = 0, l, r; i < Q; ++i)
    {
        cin >> l >> r;
        --l;
        if (r - l == 1)
        {
            cout << 1 << "\n";
            continue;
        }
        auto cmp = [&](int a, int b)
        { return out[a] > out[b]; };
        priority_queue<int, vi, decltype(cmp)> q(cmp);
        for (int j = l; j < r; ++j)
            q.push(C[j]);

        stack<int> st;
        int ans = 1;
        int current = q.top();
        q.pop();
        auto forward = [&]()
        {
            st.push(current);
            current = q.top();
            q.pop();
        };
        auto backward = [&]()
        {
            int lc = lca(current, st.top());
            ans += depth[current] - depth[lc];
            ans += depth[st.top()] - depth[lc];
            st.pop();
            current = lc;
        };
        while (sz(st) + sz(q) > 0)
        {
            if (sz(st) == 0)
            {
                forward();
            }
            else if (sz(q) == 0)
            {
                backward();
            }
            else if (sz(q) > 0 && sz(st) > 0)
            {
                if (out[lca(current, st.top())] > out[lca(current, q.top())])
                {
                    forward();
                }
                else
                {
                    backward();
                }
            }
        }

        cout << ans << "\n";
    }
}

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