Submission #1287291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287291		Faisal_Saqib	Regions (IOI09_regions)	C++20	30 / 100	374 ms	14412 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+1,R=3000+1;
int n,r,q,reg[N],dp[R],ans[R][R];
vector<int> ma[N],sub[N];
void dfs(int x,int p=-1)
{
    dp[reg[x]]++;
    for(int r1=reg[x],r2=1;r2<=r;r2++) // (N*R)
    {
        ans[r1][r2]+=dp[r2]-(r1==r2); // how many node such there are parent of x and region is r2
    }
    for(auto y:ma[x])
    {
        dfs(y,x);
    }
    dp[reg[x]]--;

}
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++)
    {
        sub[reg[i]].push_back(i);
    }
    // r<=500
    // thus we can do child[node][region]
    dfs(1);
    // get summation sz[r1]+sz[r2] (r1,r2)  summation(sz[r])*R // N*R
    // R*R ans[r1][r2] = sum(dp[x][r1]) x in sub[r1] sz[r1]
    //
    // for(int r1=1;r1<=r;r1++)
    // {

    //     for(auto x:sub[r1])
    //     {
    //         for(int r2=1;r2<=r;r2++)
    //         {
    //             ans[r1][r2]+=dp[x][r2]-(r1==r2);
    //         }
    //     }
    // }
    while(q--)
    {
        int r1,r2;
        cin>>r1>>r2;
        cout<<ans[r2][r1]<<endl;
    }
}

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