oj.uz

Submission #1016783

# Submission time Handle Problem Language Result Execution time Memory
1016783 2024-07-08T12:21:56 Z alexdd Tourism (JOI23_tourism) C++17
0 / 100
 519 ms 1048576 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 fr[100005];
int val[100005];
void baga(int le, int ri, int t)
{
    for(int i=le;i<=ri;i++)
    {
        fr[val[i]]--;
        val[i]=t;
    }
    fr[t] += ri-le+1;
}
int numara(int le)
{
    int cnt=0;
    for(int i=le;i<=n;i++)
        cnt += fr[i];
    return cnt;
}

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 || depth[x.first] < depth[y.first])) aux.first = x.first;
    else aux.first = y.first;
    if(x.second!=-1 && (y.second==-1 || depth[x.second] > depth[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,n,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});
    }
    fr[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] = numara(le) - depth[lc];
        }
    }
    for(int i=1;i<=q;i++)
        cout<<rez[i]<<"\n";
    return 0;
}

Subtask #1
0 / 5.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 Incorrect 1 ms 9820 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.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 Incorrect 1 ms 9820 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Runtime error 519 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Incorrect 105 ms 17832 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 9816 KB Output is correct
2 Runtime error 490 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 41.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 Incorrect 1 ms 9820 KB Output isn't correct
4 Halted 0 ms 0 KB -