Submission #1251040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251040		vicvic	Regions (IOI09_regions)	C++20	35 / 100	3245 ms	123160 KiB

regions

#include <bits/stdc++.h>

using namespace std;
const int NMAX=2e5, SQRT=350, KMAX=2.5e4;
int n, r, q;
vector <int> vec[NMAX+5];
vector <int> cnt[NMAX+5];
int s[NMAX+5], t[NMAX+5], timer=0, v[NMAX+5], crt, cur;
vector <int> precalc[KMAX+5];
vector <int> ord[KMAX+5];
void dfsInit (int nod)
{
    t[nod]=++timer;
    s[nod]=1;
    ord[v[nod]].push_back (t[nod]);
    for (auto adj : vec[nod])
        dfsInit (adj), s[nod]+=s[adj];
}
void dfsSqrt (int nod)
{
    if (v[nod]==crt)
        cur++;
    precalc[crt][v[nod]]+=cur;
    for (auto adj : vec[nod])
        dfsSqrt (adj);
    if (v[nod]==crt)
        cur--;
}
int main ()
{
    ios_base :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n >> r >> q;
    for (int i=1;i<=n;i++)
    {
        int p;
        if (i>=2)
            cin >> p, vec[p].push_back (i);
        cin >> v[i];
        cnt[v[i]].push_back (i);
    }
    dfsInit (1);
    for (int i=1;i<=r;i++)
    {
        if (cnt[i].size()>=SQRT)
        {
            crt=i, cur=0;
            precalc[i].resize (r+1);
            dfsInit (1);
        }
    }
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        if (cnt[x].size()<SQRT)
        {
            int ans=0;
            for (auto chestie : cnt[x])
            {
                ans+=upper_bound (ord[y].begin(), ord[y].end(), t[chestie]+s[chestie]-1)-lower_bound (ord[y].begin(), ord[y].end(), t[chestie]);
            }
            cout << ans << endl;
        }
        else
            cout << precalc[x][y] << endl;
    }
    return 0;
}

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