Submission #804490

#	Time	Username	Problem	Language	Result	Execution time	Memory
804490		mousebeaver	Tourism (JOI23_tourism)	C++14	35 / 100	5045 ms	39308 KiB

tourism

#define ll long long
#define pll pair<ll, ll>
#define INF numeric_limits<int>::max()/2
#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];
}

ll left(ll i)
{
    return 2*i;
}

ll right(ll i)
{
    return 2*i+1;
}

pll conjugate(pll a, pll b)
{
    return {max(a.first, b.first), min(a.second, b.second)};
}

pll query3(ll i, vector<pll>& s, ll a, ll b, ll l, ll r)
{
    if(l <= a && b <= r)
    {
        return s[i];
    }
    if(b < l || r < a)
    {
        return {-1, INF};
    }

    ll mid = (a+b)/2;
    return conjugate(query3(left(i), s, a, mid, l, r), query3(right(i), s, mid+1, b, l, r));
}

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]--;
    }

    segnodes = 1;
    while(2*m > segnodes)
    {
        segnodes *= 2;
    }
    vector<pll> s3(segnodes, {-1, INF}); //Max, min
    if(sub3)
    {
        for(ll i = 0; i < m; i++)
        {
            s3[i+segnodes/2].first = depth[c[i]];
            s3[i+segnodes/2].second = depth[c[i]];
        }
        for(ll i = segnodes/2-1; i > 0; i--)
        {
            s3[i].first = max(s3[left(i)].first, s3[right(i)].first);
            s3[i].second = min(s3[left(i)].second, s3[right(i)].second);
        }
    }

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

        if(left == right)
        {
            cout<<1<<"\n";
            continue;
        }
        if(sub3)
        {
            pll range = query3(1, s3, 1, segnodes/2, left+1, right+1);
            cout<<range.first+1-range.second<<"\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: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41