oj.uz

Submission #895917

# Submission time Handle Problem Language Result Execution time Memory
895917 2023-12-31T05:25:28 Z Tuanlinh123 Tourism (JOI23_tourism) C++17
0 / 100
 187 ms 16344 KB 
#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)
{
    // cout << i << " " << val << "\n";
    for (; i<=n; 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;
    // cout << i << " " << St[i] << " " << Start << " " << End << " " << l << " " << r << " " << val << "\n";
    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, i);
    }
    for (ll i=1; i<=q; i++)
        cout << ans[i] << "\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Incorrect 2 ms 9052 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Incorrect 2 ms 9052 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Incorrect 2 ms 8988 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 135 ms 15280 KB Output is correct
3 Incorrect 187 ms 16344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Incorrect 2 ms 9052 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Incorrect 2 ms 9052 KB Output isn't correct
5 Halted 0 ms 0 KB -