Submission #1287290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287290		Faisal_Saqib	Regions (IOI09_regions)	C++20	30 / 100	375 ms	14404 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 all pair with a fixed r1, We can do it we keep 
// if we Virtual Tree technique again then O(R*sz[r1] + summation(sz[r2]) ) lgn for each r1 and total possible are N/B
// (N*(R+1)*N)/Q = B*B 
// 
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+1,R=500+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++)
    {
        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