oj.uz

Submission #1016794

# Submission time Handle Problem Language Result Execution time Memory
1016794 2024-07-08T12:27:52 Z alexdd Tourism (JOI23_tourism) C++17
52 / 100
 5000 ms 24660 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
vector<int> con[100005];
int v[100005];
int rez[100005];
int anc[100005][17];
int tin[100005],tout[100005],timer;
vector<pair<int,int>> qrys[100005];

int aib[100015];
int qry_aib(int poz)
{
    poz+=2;
    int aux=0;
    for(int i=poz;i<=m+5;i+=(i&(-i)))
        aux += aib[i];
    return aux;
}
void upd_aib(int poz, int newv)
{
    poz+=2;
    for(int i=poz;i>0;i-=(i&(-i)))
        aib[i] += newv;
}

int val[100005];
void baga(int le, int ri, int t)
{
    for(int i=le;i<=ri;i++)
    {
        upd_aib(val[i],-1);
        val[i]=t;
    }
    upd_aib(t,ri-le+1);
}

int depth[100005], siz[100005], head[100005], parent[100005], pos[100005], curpos;
void dfs(int nod)
{
    siz[nod]=1;
    tin[nod]=++timer;
    for(auto adj:con[nod])
    {
        if(adj!=parent[nod])
        {
            parent[adj]=nod;
            depth[adj]=depth[nod]+1;
            dfs(adj);
            siz[nod]+=siz[adj];
        }
    }
    tout[nod]=++timer;
}
void decompose(int nod, int chead)
{
    pos[nod]=++curpos;
    head[nod]=chead;
    int heavy=-1,maxc=-1;
    for(auto adj:con[nod])
        if(adj!=parent[nod] && siz[adj]>maxc)
            maxc=siz[adj], heavy=adj;
    if(heavy!=-1)
        decompose(heavy,chead);
    for(auto adj:con[nod])
        if(adj!=parent[nod] && adj!=heavy)
            decompose(adj,adj);
}
void upd_hld(int b, int t)
{
    for(;head[1]!=head[b];b=parent[head[b]])
    {
        baga(pos[head[b]], pos[b], t);
    }
    baga(pos[1],pos[b],t);
}

pair<int,int> aint[270000];
pair<int,int> combine(pair<int,int> x, pair<int,int> y)
{
    pair<int,int> aux;
    if(x.first!=-1 && (y.first==-1 || tin[x.first] < tin[y.first])) aux.first = x.first;
    else aux.first = y.first;
    if(x.second!=-1 && (y.second==-1 || tin[x.second] > tin[y.second])) aux.second = x.second;
    else aux.second = y.second;
    return aux;
}
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod] = {v[st],v[st]};
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod] = combine(aint[nod*2], aint[nod*2+1]);
}
pair<int,int> qry(int nod, int st, int dr, int le, int ri)
{
    if(le>ri)
        return {-1,-1};
    if(le==st && dr==ri)
        return aint[nod];
    int mij=(st+dr)/2;
    return combine(qry(nod*2,st,mij,le,min(mij,ri)),
                   qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));

}
bool isanc(int x, int y)
{
    return (tin[x]<=tin[y] && tout[x]>=tout[y]);
}
int lca(int x, int y)
{
    if(isanc(x,y))
        return x;
    if(isanc(y,x))
        return y;
    for(int p=16;p>=0;p--)
        if(!isanc(anc[x][p],y))
            x = anc[x][p];
    return anc[x][0];
}
int qry_lca(int le, int ri)
{
    pair<int,int> x = qry(1,1,m,le,ri);
    return lca(x.first, x.second);
}
signed main()
{
    cin>>n>>m>>q;
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    dfs(1);
    decompose(1,1);

    for(int i=1;i<=n;i++)
        anc[i][0] = parent[i];
    anc[1][0]=1;
    for(int p=1;p<17;p++)
        for(int i=1;i<=n;i++)
            anc[i][p] = anc[anc[i][p-1]][p-1];

    for(int i=1;i<=m;i++)
        cin>>v[i];
    build(1,1,m);
    for(int i=1;i<=q;i++)
    {
        cin>>a>>b;
        qrys[b].push_back({a,i});
    }
    upd_aib(0,n);
    for(int i=1;i<=m;i++)
    {
        upd_hld(v[i],i);
        for(auto [le,id]:qrys[i])
        {
            int lc = qry_lca(le,i);
            rez[id] = qry_aib(le) - depth[lc];
        }
    }
    for(int i=1;i<=q;i++)
        cout<<rez[i]<<"\n";
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 1 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 10072 KB Output is correct
9 Correct 2 ms 9816 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 3 ms 9804 KB Output is correct
16 Correct 2 ms 9816 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9816 KB Output is correct
19 Correct 2 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 2 ms 9820 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 3 ms 9820 KB Output is correct
25 Correct 2 ms 9820 KB Output is correct
26 Correct 2 ms 9680 KB Output is correct
27 Correct 2 ms 9820 KB Output is correct
28 Correct 2 ms 9820 KB Output is correct
29 Correct 2 ms 9820 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 1 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 10072 KB Output is correct
9 Correct 2 ms 9816 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 3 ms 9804 KB Output is correct
16 Correct 2 ms 9816 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9816 KB Output is correct
19 Correct 2 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 2 ms 9820 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 3 ms 9820 KB Output is correct
25 Correct 2 ms 9820 KB Output is correct
26 Correct 2 ms 9680 KB Output is correct
27 Correct 2 ms 9820 KB Output is correct
28 Correct 2 ms 9820 KB Output is correct
29 Correct 2 ms 9820 KB Output is correct
30 Correct 3 ms 9820 KB Output is correct
31 Correct 4 ms 9820 KB Output is correct
32 Correct 4 ms 9820 KB Output is correct
33 Correct 4 ms 9816 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 4 ms 9820 KB Output is correct
36 Correct 4 ms 9820 KB Output is correct
37 Correct 4 ms 9820 KB Output is correct
38 Correct 9 ms 9884 KB Output is correct
39 Correct 8 ms 10076 KB Output is correct
40 Correct 8 ms 10092 KB Output is correct
41 Correct 9 ms 10076 KB Output is correct
42 Correct 9 ms 10076 KB Output is correct
43 Correct 7 ms 9820 KB Output is correct
44 Correct 7 ms 9988 KB Output is correct
45 Correct 5 ms 9864 KB Output is correct
46 Correct 6 ms 10032 KB Output is correct
47 Correct 6 ms 9816 KB Output is correct
48 Correct 5 ms 9820 KB Output is correct
49 Correct 8 ms 9820 KB Output is correct
50 Correct 4 ms 9820 KB Output is correct
51 Correct 4 ms 9820 KB Output is correct
52 Correct 4 ms 9820 KB Output is correct
53 Correct 5 ms 9820 KB Output is correct
54 Correct 4 ms 9820 KB Output is correct
55 Correct 4 ms 9820 KB Output is correct
56 Correct 3 ms 9820 KB Output is correct
57 Correct 3 ms 9900 KB Output is correct
58 Correct 4 ms 9820 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9820 KB Output is correct
4 Execution timed out 5091 ms 23668 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 58 ms 16804 KB Output is correct
3 Correct 76 ms 18052 KB Output is correct
4 Correct 69 ms 18320 KB Output is correct
5 Correct 104 ms 21332 KB Output is correct
6 Correct 102 ms 21328 KB Output is correct
7 Correct 107 ms 21356 KB Output is correct
8 Correct 114 ms 21328 KB Output is correct
9 Correct 100 ms 21328 KB Output is correct
10 Correct 105 ms 21360 KB Output is correct
11 Correct 102 ms 21388 KB Output is correct
12 Correct 109 ms 21228 KB Output is correct
13 Correct 113 ms 21624 KB Output is correct
14 Correct 118 ms 22352 KB Output is correct
15 Correct 174 ms 24660 KB Output is correct
16 Correct 111 ms 21584 KB Output is correct
17 Correct 108 ms 21588 KB Output is correct
18 Correct 121 ms 21588 KB Output is correct
19 Correct 557 ms 21328 KB Output is correct
20 Correct 500 ms 21404 KB Output is correct
21 Correct 388 ms 21332 KB Output is correct
22 Correct 504 ms 21404 KB Output is correct
23 Correct 466 ms 21404 KB Output is correct
24 Correct 447 ms 21248 KB Output is correct
25 Correct 423 ms 21324 KB Output is correct
26 Correct 681 ms 21328 KB Output is correct
27 Correct 432 ms 21432 KB Output is correct
28 Correct 348 ms 21328 KB Output is correct
29 Correct 543 ms 21432 KB Output is correct
30 Correct 749 ms 21604 KB Output is correct
31 Correct 417 ms 21588 KB Output is correct
32 Correct 487 ms 21976 KB Output is correct
33 Correct 428 ms 22924 KB Output is correct
34 Correct 894 ms 24604 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 3 ms 9816 KB Output is correct
4 Correct 142 ms 20004 KB Output is correct
5 Correct 152 ms 20052 KB Output is correct
6 Correct 162 ms 23124 KB Output is correct
7 Correct 168 ms 23632 KB Output is correct
8 Correct 183 ms 23660 KB Output is correct
9 Correct 175 ms 23636 KB Output is correct
10 Correct 175 ms 23636 KB Output is correct
11 Correct 168 ms 23636 KB Output is correct
12 Correct 163 ms 23632 KB Output is correct
13 Correct 171 ms 23636 KB Output is correct
14 Correct 73 ms 14004 KB Output is correct

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 1 ms 9820 KB Output is correct
4 Correct 2 ms 9820 KB Output is correct
5 Correct 2 ms 9820 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 2 ms 10072 KB Output is correct
9 Correct 2 ms 9816 KB Output is correct
10 Correct 2 ms 9820 KB Output is correct
11 Correct 2 ms 9820 KB Output is correct
12 Correct 2 ms 9820 KB Output is correct
13 Correct 2 ms 9820 KB Output is correct
14 Correct 2 ms 9820 KB Output is correct
15 Correct 3 ms 9804 KB Output is correct
16 Correct 2 ms 9816 KB Output is correct
17 Correct 2 ms 9820 KB Output is correct
18 Correct 2 ms 9816 KB Output is correct
19 Correct 2 ms 9820 KB Output is correct
20 Correct 2 ms 9820 KB Output is correct
21 Correct 2 ms 9820 KB Output is correct
22 Correct 2 ms 9820 KB Output is correct
23 Correct 2 ms 9820 KB Output is correct
24 Correct 3 ms 9820 KB Output is correct
25 Correct 2 ms 9820 KB Output is correct
26 Correct 2 ms 9680 KB Output is correct
27 Correct 2 ms 9820 KB Output is correct
28 Correct 2 ms 9820 KB Output is correct
29 Correct 2 ms 9820 KB Output is correct
30 Correct 3 ms 9820 KB Output is correct
31 Correct 4 ms 9820 KB Output is correct
32 Correct 4 ms 9820 KB Output is correct
33 Correct 4 ms 9816 KB Output is correct
34 Correct 4 ms 9820 KB Output is correct
35 Correct 4 ms 9820 KB Output is correct
36 Correct 4 ms 9820 KB Output is correct
37 Correct 4 ms 9820 KB Output is correct
38 Correct 9 ms 9884 KB Output is correct
39 Correct 8 ms 10076 KB Output is correct
40 Correct 8 ms 10092 KB Output is correct
41 Correct 9 ms 10076 KB Output is correct
42 Correct 9 ms 10076 KB Output is correct
43 Correct 7 ms 9820 KB Output is correct
44 Correct 7 ms 9988 KB Output is correct
45 Correct 5 ms 9864 KB Output is correct
46 Correct 6 ms 10032 KB Output is correct
47 Correct 6 ms 9816 KB Output is correct
48 Correct 5 ms 9820 KB Output is correct
49 Correct 8 ms 9820 KB Output is correct
50 Correct 4 ms 9820 KB Output is correct
51 Correct 4 ms 9820 KB Output is correct
52 Correct 4 ms 9820 KB Output is correct
53 Correct 5 ms 9820 KB Output is correct
54 Correct 4 ms 9820 KB Output is correct
55 Correct 4 ms 9820 KB Output is correct
56 Correct 3 ms 9820 KB Output is correct
57 Correct 3 ms 9900 KB Output is correct
58 Correct 4 ms 9820 KB Output is correct
59 Correct 2 ms 9820 KB Output is correct
60 Correct 2 ms 9820 KB Output is correct
61 Correct 3 ms 9820 KB Output is correct
62 Execution timed out 5091 ms 23668 KB Time limit exceeded
63 Halted 0 ms 0 KB -