Submission #804408

#	Time	Username	Problem	Language	Result	Execution time	Memory
804408		mousebeaver	Tourism (JOI23_tourism)	C++14	28 / 100	5103 ms	34956 KiB

tourism

#define ll long long
#define INF numeric_limits<ll>::max()
#include <bits/stdc++.h>
using namespace std;

void init(ll i, vector<ll>& depth, vector<vector<ll>>& adjlist, vector<bool>& visited, vector<ll>& subtree, vector<vector<ll>>& jump)
{
    visited[i] = true;

    for(ll j : adjlist[i])
    {
        if(visited[j])
        {
            jump[0][i] = j;
            depth[i] = depth[j]+1;
        }
    }
    for(ll j : adjlist[i])
    {
        if(!visited[j])
        {
            init(j, depth, adjlist, visited, subtree, jump);
            subtree[i] += subtree[j];
        }
    }
}

ll lift(ll a, vector<vector<ll>>& jump, ll dist)
{
    for(ll i = jump.size()-1; i >= 0 && a != -1; i--)
    {
        if(((1<<i)&dist) != 0)
        {
            a = jump[i][a];
        }
    }
    return a;
}

ll lca(ll a, ll b, vector<vector<ll>>& jump, vector<ll>& depth)
{
    if(depth[a] < depth[b])
        swap(a, b);
    a = lift(a, jump, depth[a]-depth[b]);

    if(a == b)
    {
        return a;
    }

    for(ll j = jump.size()-1; j >= 0; j--)
    {
        if(jump[j][a] != jump[j][b])
        {
            a = jump[j][a];
            b = jump[j][b];
        }
    }
    return jump[0][a];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n, m, q;
    cin>>n>>m>>q;
    vector<vector<ll>> adjlist(n, vector<ll> (0));
    bool sub3 = true;
    for(ll i = 0; i < n-1; i++)
    {
        ll a, b;
        cin>>a>>b;
        a--; b--;
        if(a != i || b != i+1)
        {
            sub3 = false;
        }
        adjlist[a].push_back(b);
        adjlist[b].push_back(a);
    }

    ll segnodes = 1;
    ll logdepth = 0;
    while(2*n > segnodes)
    {
        segnodes *= 2;
        logdepth++;
    }
    vector<vector<ll>> jump(logdepth, vector<ll> (n, -1));

    vector<ll> subtree(n, 1);
    vector<bool> visited(n, false);
    vector<ll> depth(n, 0);
    init(0, depth, adjlist, visited, subtree, jump);

    for(ll i = 1; i < logdepth; i++)
    {
        for(ll j = 0; j < n; j++)
        {
            if(jump[i-1][j] != -1)
            {
                jump[i][j] = jump[i-1][jump[i-1][j]];
            }
        }
    }

    vector<ll> c(m);
    for(ll i = 0; i < m; i++)
    {
        cin>>c[i];
        c[i]--;
    }

    for(ll x = 0; x < q; x++)
    {
        ll left, right;
        cin>>left>>right;
        left--; right--;

        if(left == right)
        {
            cout<<1<<"\n";
            continue;
        }
        if(sub3)
        {
            ll top = INF;
            ll bottom = -1;
            for(ll i = left; i <= right; i++)
            {
                top = min(top, depth[c[i]]);
                bottom = max(bottom, depth[c[i]]);
            }
            cout<<bottom+1-top<<"\n";
            continue;
        }

        ll l = lca(c[left], c[left+1], jump, depth);
        for(ll i = left+2; i <= right; i++)
        {
            l = lca(l, c[i], jump, depth);
        }

        visited.assign(n, false);
        visited[l] = true;
        ll counter = 1;
        for(ll i = left; i <= right; i++)
        {
            ll node = c[i];
            while(!visited[node])
            {
                visited[node] = true;
                counter++;
                node = jump[0][node];
            }
        }
        cout<<counter<<"\n";
    }


    return 0;  
}

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