Submission #1136992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136992		denislav	Tourism (JOI23_tourism)	C++20	100 / 100	835 ms	22088 KiB

tourism

# include <iostream>
# include <vector>
# include <set>
# include <array>
using namespace std;

const int MAX=1e5+11;

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

vector<pair<int,int>> z[MAX];
int out[MAX];

void read()
{
    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;
        if(l==r) out[i]=1;
        else z[r].push_back({l,i});
    }
}

int h[MAX];
int sz[MAX];

void dfs_sz(int curr, int par)
{
    sz[curr]=1;
    for(int nxt: adj[curr])
    {
        if(nxt==par) continue;

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

int ct=0;
int in[MAX];
int id[MAX];
int lead[MAX];
int up[MAX];

void dfs_hld(int curr, int par, int top)
{
    id[curr]=++ct;
    in[ct]=curr;
    lead[curr]=top;
    up[curr]=par;

    int hv=-1;
    for(int nxt: adj[curr])
    {
        if(nxt==par) continue;

        if(hv==-1 or sz[nxt]>sz[hv]) hv=nxt;
    }

    if(hv!=-1) dfs_hld(hv,curr,top);
    for(int nxt: adj[curr])
    {
        if(nxt==par or nxt==hv) continue;
        dfs_hld(nxt,curr,nxt);
    }
}


void prepare_hld()
{
    dfs_sz(1,0);
    dfs_hld(1,0,1);
}

struct Fenwick
{
    int tree[MAX];

    void init()
    {
        for(int i=0;i<=m;i++) tree[i]=0;
    }

    void update(int u, int d)
    {
        for(int i=u;i<=m;i=(i|(i+1)))
        {
            tree[i]+=d;
        }
    }

    int query(int u)
    {
        int ans=0;
        for(int i=u;i>=0;i=(i&(i+1))-1)
        {
            ans+=tree[i];
        }
        return ans;
    }

    int query(int l, int r)
    {
        if(l>r) return 0;
        return query(r)-query(l-1);
    }
}tree;

set<array<int,3>> s;

void change(int l, int r, int val)
{
    vector<array<int,3>> add,rem;
    auto it=s.lower_bound({l,r,val});
    if(it!=s.begin()) it--;

    while(it!=s.end() and (*it)[0]<=r)
    {
        int le=(*it)[0],ri=(*it)[1],val2=(*it)[2];
        if(ri<l)
        {
            it++;
            continue;
        }

        rem.push_back(*it);
        if(le<l) add.push_back({le,l-1,val2});
        if(r<ri) add.push_back({r+1,ri,val2});
        it++;
    }

    add.push_back({l,r,val});
    for(array<int,3> p: add)
    {
        s.insert(p);
        tree.update(p[2],p[1]-p[0]+1);
    }
    for(array<int,3> p: rem)
    {
        s.erase(p);
        tree.update(p[2],-(p[1]-p[0]+1));
    }

    /*
    cout<<"->"<<l<<" "<<r<<"\n";
    for(array<int,3> r: s) cout<<r[0]<<" "<<r[1]<<" "<<r[2]<<"\n";
    cout<<"\n";
    */
}

void path(int u, int v, int val)
{
    while(lead[u]!=lead[v])
    {
        if(h[lead[u]]<h[lead[v]]) swap(u,v);
        change(id[lead[u]],id[u],val);
        u=up[lead[u]];
    }

    if(h[u]>h[v]) swap(u,v);
    change(id[u],id[v],val);
}

void solve()
{
    tree.init();
    s.insert({1,m,0});
    tree.update(0,m);

    for(int i=2;i<=m;i++)
    {
        path(c[i-1],c[i],i-1);

        for(pair<int,int> pa: z[i])
        {
            out[pa.second]=tree.query(pa.first,m);
        }
    }

    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);

    read();
    prepare_hld();
    solve();

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41