oj.uz

Submission #1013718

# Submission time Handle Problem Language Result Execution time Memory
1013718 2024-07-04T03:25:23 Z 12345678 Tourism (JOI23_tourism) C++17
0 / 100
 159 ms 13056 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, kx=17;

int n, m, q, u, v, in[nx], out[nx], pa[nx][kx], t, c[nx], l=1, r, a[nx], b[nx], ans, lvl[nx];
vector<int> d[nx];

void dfs(int u, int p)
{
    pa[u][0]=p;
    lvl[u]=lvl[p]+1;
    for (int i=1; i<kx; i++) pa[u][i]=pa[pa[u][i-1]][i-1];
    in[u]=++t;
    for (auto v:d[u]) if (v!=p) dfs(v, u);
    out[u]=t;
}

struct segtree
{
    int d[4*nx];
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]+=vl, void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=d[2*i]+d[2*i+1];
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
    }
} s;

int getlca(int u, int cur)
{
    if (s.query(1, n, 1, in[u], out[u])==cur) return u;
    for (int i=kx-1; i>=0; i--) if (s.query(1, n, 1, in[u], out[u])!=cur) u=pa[u][i];
    return pa[u][0];
}

void add(int u)
{
    if (l==r) return ans=1, s.update(1, n, 1, in[u], 1), void();
    int v=u, lca=getlca(c[l], r-l);
    if (s.query(1, n, 1, in[u], out[u])>0) 
    {
        if (lvl[lca]<=lvl[u]) return s.update(1, n, 1, in[u], 1), void();
        ans+=lvl[lca]-lvl[u];
        s.update(1, n, 1, in[u], 1);
        return;
    }
    for (int i=kx-1; i>=0; i--) if (s.query(1, n, 1, in[pa[v][i]], out[pa[v][i]])==0) v=pa[v][i];
    if (lvl[lca]<lvl[v]) ans+=lvl[u]-lvl[v]+1, s.update(1, n, 1, in[u], 1);
    else ans+=lvl[u]-lvl[v]+1+lvl[lca]-lvl[v]+1, s.update(1, n, 1, in[u], 1);
}

void rem(int u)
{
    s.update(1, n, 1, in[u], -1);
    int v=u, lca=getlca(c[l], r-l+1);
    if (s.query(1, n, 1, in[u], out[u])>0) 
    {
        if (lvl[lca]<=lvl[u]) return;
        ans-=lvl[lca]-lvl[u];
        return;
    }
    for (int i=kx-1; i>=0; i--) if (s.query(1, n, 1, in[pa[v][i]], out[pa[v][i]])==0) v=pa[v][i];
    //cout<<"rem "<<u<<' '<<v<<' '<<lca<<'\n';
    if (lvl[lca]<lvl[v]) ans-=lvl[u]-lvl[v]+1;
    else ans-=(lvl[u]-lvl[v]+1)+lvl[lca]-lvl[v]+1;

}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>q;
    for (int i=1; i<n; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    dfs(1, 1);
    for (int i=1; i<=m; i++) cin>>c[i];
    for (int i=1; i<=q; i++)
    {
        cin>>a[i]>>b[i];
        while (r<b[i]) add(c[++r]); //cout<<l<<' '<<r<<' '<<ans<<'\n';
        while (l<a[i]) rem(c[l++]); //cout<<l<<' '<<r<<' '<<ans<<'\n';
        cout<<ans<<'\n';
    }
}

/*
7 6 6
1 2
1 3
2 4
2 5
3 6
3 7
2 3 6 4 5 7
1 1
2 2
3 3
4 4
5 5
6 6
*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 1 ms 2808 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Incorrect 159 ms 13056 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

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