oj.uz

Submission #1013723

# Submission time Handle Problem Language Result Execution time Memory
1013723 2024-07-04T03:39:25 Z 12345678 Tourism (JOI23_tourism) C++17
18 / 100
 5000 ms 19024 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=1, 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[pa[u][i]], out[pa[u][i]])!=cur) u=pa[u][i];
    return pa[u][0];
}

void add(int u)
{
    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];
    v=pa[v][0];
    if (lvl[lca]<=lvl[v]) ans+=lvl[u]-lvl[v], s.update(1, n, 1, in[u], 1);
    else ans+=lvl[u]-lvl[v]+lvl[pa[lca][0]]-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];
    v=pa[v][0];
    if (lvl[lca]<=lvl[v]) ans-=lvl[u]-lvl[v];
    else ans-=lvl[u]-lvl[v]+lvl[pa[lca][0]]-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];
    ans=1;
    s.update(1, n, 1, in[c[1]], 1);
    for (int i=1; i<=q; i++)
    {
        cin>>a[i]>>b[i];
        while (l>a[i]) add(c[--l]);
        while (r<b[i]) add(c[++r]);
        while (l<a[i]) rem(c[l++]);
        while (r>b[i]) rem(c[r--]);
        cout<<ans<<'\n';
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2652 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 2652 KB Output is correct
2 Incorrect 1 ms 2652 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
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 185 ms 10412 KB Output is correct
3 Correct 256 ms 11356 KB Output is correct
4 Correct 199 ms 12712 KB Output is correct
5 Correct 139 ms 16976 KB Output is correct
6 Correct 217 ms 17012 KB Output is correct
7 Correct 245 ms 16928 KB Output is correct
8 Correct 271 ms 16980 KB Output is correct
9 Correct 331 ms 17016 KB Output is correct
10 Correct 320 ms 17020 KB Output is correct
11 Correct 376 ms 16788 KB Output is correct
12 Correct 305 ms 16976 KB Output is correct
13 Correct 298 ms 17236 KB Output is correct
14 Correct 311 ms 17492 KB Output is correct
15 Correct 227 ms 19024 KB Output is correct
16 Correct 304 ms 17144 KB Output is correct
17 Correct 302 ms 17000 KB Output is correct
18 Correct 294 ms 17236 KB Output is correct
19 Correct 153 ms 16980 KB Output is correct
20 Correct 200 ms 16984 KB Output is correct
21 Correct 232 ms 16976 KB Output is correct
22 Correct 276 ms 16992 KB Output is correct
23 Correct 282 ms 16980 KB Output is correct
24 Correct 311 ms 16984 KB Output is correct
25 Correct 339 ms 16964 KB Output is correct
26 Correct 495 ms 17000 KB Output is correct
27 Correct 476 ms 16976 KB Output is correct
28 Correct 536 ms 16980 KB Output is correct
29 Correct 579 ms 17236 KB Output is correct
30 Correct 638 ms 17060 KB Output is correct
31 Correct 532 ms 17232 KB Output is correct
32 Correct 586 ms 17540 KB Output is correct
33 Correct 493 ms 17912 KB Output is correct
34 Correct 396 ms 19024 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 19 ms 2824 KB Output is correct
4 Execution timed out 5096 ms 10972 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

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