Submission #895947

#	Time	Username	Problem	Language	Result	Execution time	Memory
895947		Tuanlinh123	Tourism (JOI23_tourism)	C++17	100 / 100	410 ms	30804 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, St[maxn*4], bit[maxn], c[maxn], ans[maxn];
ll Time, tin[maxn], h[maxn], pa[maxn], dep[maxn], child[maxn], big[maxn];

void update(ll i, ll val)
{
    for (; i<=m; i+=i&(-i))
        bit[i]+=val;
}

ll query(ll l, ll r)
{
    ll ans=0; l--;
    for (; r; r-=r&(-r))
        ans+=bit[r];
    for (; l; l-=l&(-l))
        ans-=bit[l];
    return ans;
}

void update(ll i, ll Start, ll End, ll l, ll r, ll val)
{
    if (Start>r || End<l)
        return;
    if (Start>=l && End<=r && St[i]!=-1)
    {
        if (St[i]) update(St[i], -(End-Start+1));
        update(val, End-Start+1);
        St[i]=val;
        return;
    }
    if (St[i]!=-1) St[i*2]=St[i*2+1]=St[i];
    ll mid=(Start+End)/2;
    if (mid>=l) update(i*2, Start, mid, l, r, val);
    if (mid+1<=r) update(i*2+1, mid+1, End, l, r, val);
    if (St[i*2]==St[i*2+1]) St[i]=St[i*2];
    else St[i]=-1;
}

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

void dfs2(ll u)
{
    tin[u]=++Time;
    if (u==big[pa[u]])
        h[u]=h[pa[u]];
    else h[u]=u;
    if (big[u]) dfs2(big[u]);
    for (ll v:A[u])
        if (v!=pa[u] && v!=big[u])
            dfs2(v);
}

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

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); dfs2(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, m);
    }
    for (ll i=1; i<=q; i++)
        cout << ans[i] << "\n";
}

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