Submission #895939

#	Time	Username	Problem	Language	Result	Execution time	Memory
895939		Tuanlinh123	Tourism (JOI23_tourism)	C++17	10 / 100	5090 ms	18748 KiB

tourism

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=100005;
vector <ll> A[maxn];
vector <pll> L[maxn];
ll n, m, q, c[maxn], a[maxn], ans[maxn], pa[maxn], dep[maxn];

void dfs(ll u)
{
    for (ll v:A[u])
        if (v!=pa[u])
        {
            dep[v]=dep[u]+1; 
            pa[v]=u, dfs(v);
        }
}

void update(ll u, ll v, ll val)
{
    for (; u!=v; u=pa[u])
    {
        if (dep[u]<dep[v]) swap(u, v);
        a[u]=val;
    }
    a[u]=val;
}

ll query(ll l, ll r)
{
    ll ans=0;
    for (ll i=1; i<=n; i++)
        if (l<=a[i] && a[i]<=r)
            ans++;
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for (ll i=1; i<n; i++)
    {
        ll u, v; cin >> u >> v;
        A[u].pb(v); A[v].pb(u);
    }
    dfs(1); 
    for (ll i=1; i<=m; i++)
        cin >> c[i];
    for (ll i=1; i<=q; i++)
    {
        ll l, r; cin >> l >> r;
        L[r].pb({l, i});
    }
    for (ll i=1; i<=m; i++)
    {
        if (i>1) update(c[i-1], c[i], i-1);
        update(c[i], c[i], i);
        for (auto &[l, idx]:L[i])
            ans[idx]=query(l, i);
    }
    for (ll i=1; i<=q; i++)
        cout << ans[i] << "\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