Submission #1287369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287369		Faisal_Saqib	Regions (IOI09_regions)	C++20	55 / 100	6213 ms	77828 KiB

regions

/*
Can store atmost 1e7 numbers of ll, and abuot 2e7 of int in memory

Fastest way to compute answer for any two region is to use Virtual Tree Trick.
(r1,r2) can be done in O( (sz[r1]+sz[r2]) lg n) , lgn is for sorting,


For computing for all pair, We can do it we O(N*R) 
// 
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+2,R=25000+2,B=1500,BN=(N+B)/B +1;
int n,r,q,par[N],reg[N],dp[R],tot[R],cpp[R][BN],pcp[BN][R],sz[R],tin[N],tout[N],tasp=0;
vector<int> ma[N],bt,sv;
vector<vector<int>> sub[R];
void dfs(int x,int p=-1)
{
    tin[x]=++tasp;
    dp[reg[x]]++;
    par[x]=p;
    if(sz[reg[x]]<=B)
        sub[reg[x]].push_back({tin[x],-x});
    for(int r1=reg[x],i2=0;i2<bt.size();i2++) // (N*R)
    {
        int r2=bt[i2];
        pcp[i2][r1]+=dp[r2]-(r1==r2); // how many node such there are parent of x and region is r2
    }
    tot[reg[x]]++;
    for(auto y:ma[x])
    {
        sv.clear();
        for(int i=0;i<bt.size();i++)
        {
            sv.push_back(tot[bt[i]]);
        }
        dfs(y,x);
        for(int i=0;i<bt.size();i++)
        {
            cpp[reg[x]][i]=tot[bt[i]]-sv[i];
        }
    }
    dp[reg[x]]--;
    tout[x]=tasp;
    if(sz[reg[x]]<=B)
        sub[reg[x]].push_back({tout[x],x});
}
int fen[N];
void add(int x,int v=1)
{
    while(x>0)
    {
        fen[x]+=v;
        x-=(x&-x);
    }
}
int query(int x)
{
    int ans=0;
    while(x<N)
    {
        ans+=fen[x];
        x+=x&-x;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>r>>q;
    for(int i=1;i<=n;i++)
    {
        if(i==1)
        {
            cin>>reg[i];
            continue;
        }
        int x;
        cin>>x>>reg[i];
        ma[x].push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        sz[reg[i]]++;
    }
    for(int i=1;i<=r;i++)
    {
        if(sz[i]>B)
        {
            bt.push_back(i);
        }
    }
    dfs(1);

    while(q--)
    {
        int r1,r2;
        cin>>r1>>r2;
        if(sz[r1]>B)
        {
            int i2=lower_bound(begin(bt),end(bt),r1)-begin(bt);
            cout<<pcp[i2][r2]<<endl;
        }
        else if(sz[r2]>B)
        {
            int i2=lower_bound(begin(bt),end(bt),r2)-begin(bt);
            cout<<cpp[r1][i2]<<endl;
        }
        else
        {
            int ans=0;
            // need a fenwick tree of 10^5 = 15
            int p1=0,p2=0;
            while(p1<sub[r1].size() and p2<sub[r2].size())
            {
                if(sub[r1][p1]<=sub[r2][p2])
                {
                    if(sub[r1][p1][1]<0)
                    {
                        add(tout[-sub[r1][p1][1]],1);
                    }
                    else
                    {
                        add(sub[r1][p1][0],-1);
                    }
                    p1++;
                }
                else
                {
                    if(sub[r2][p2][1]<0)
                    {
                        ans+=query(tout[-sub[r2][p2][1]]);
                    }
                    else
                    {
                    }
                    p2++;
                }
            }
            while(p1<sub[r1].size())
            {
                if(sub[r1][p1][1]<0)
                {
                    add(tout[-sub[r1][p1][1]],1);
                }
                else
                {
                    add(sub[r1][p1][0],-1);
                }
                p1++;
            }
            cout<<ans<<endl;
        }
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 85