Submission #1129090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129090		denislav	Tourism (JOI23_tourism)	C++20	Compilation error	0 ms	0 KiB

tourism

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;

const int MAX=1e5+11;

int n,m,q;
vector<int> adj[MAX];
int c[MAX];

int h[MAX];
int up[MAX];
void dfs_h(int curr, int par)
{
    up[curr]=par;
    for(int nxt: adj[curr])
    {
        if(nxt==par) continue;

        h[nxt]=h[curr]+1;
        dfs_h(nxt,curr);
    }
}

struct query
{
    int l,r,id;
}z[MAX];
int out[MAX];

int block_sz;
int get_block(int x)
{
    if(x%block_sz==0) return x/block_sz;
    return x/block_sz+1;
}

int occ[MAX];
int ans=0;

void add_vert(int u)
{
    if(occ[u]==0) ans++;
    occ[u]++;
}

void del_vert(int u)
{
    if(occ[u]==1) ans--;
    occ[u]--;
}

void path(int u, int v, bool add)
{
    //cout<<"-->"<<u<<" "<<v<<" "<<add<<"\n";

    while(u!=v)
    {
        if(h[u]>=h[v])
        {
            //cout<<"->"<<u<<"\n";
            if(add) add_vert(u);
            else del_vert(u);
            u=up[u];
        }
        else
        {
            //cout<<"->"<<u<<"\n";
            if(add) add_vert(v);
            else del_vert(v);
            v=up[v];
        }
    }

    //cout<<"->"<<u<<"\n";
    if(add) add_vert(u);
    else del_vert(u);
}

void Mo()
{
    block_sz=sqrt(m);
    sort(z+1,z+1+q, [&](query A, query B)
    {
        int blockA=get_block(A.l),blockB=get_block(B.l);
        if(blockA!=blockB) return blockA<blockB;
        return A.r<B.r;
    });

    int l=1,r=1;
    for(int i=1;i<=q;i++)
    {
        //cout<<":"<<z[i].l<<" "<<z[i].r<<"\n";

        while(r<z[i].r) {path(c[r],c[r+1],1);r++;}
        while(l>z[i].l) {path(c[l-1],c[l],1);l--;}
        while(r>z[i].r) {path(c[r-1],c[r],0);r--;}
        while(l<z[i].l) {path(c[l],c[l+1],0);l++;}

        out[z[i].id]=max(1,ans);
        //cout<<"\n";
    }

    for(int i=1;i<=q;i++) cout<<out[i]<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>m>>q;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=m;i++) cin>>c[i];
    for(int i=1;i<=q;i++)
    {
        int l,r;
        cin>>l>>r;
        z[i]={l,r,i};
    }

    dfs_h(1,0);
    Mo();

    return 0;
}

Compilation message (stderr)

tourism.cpp: In function 'void Mo()':
tourism.cpp:83:14: error: 'sqrt' was not declared in this scope
   83 |     block_sz=sqrt(m);
      |              ^~~~