Submission #1265719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265719		kaloyan	Regions (IOI09_regions)	C++20	0 / 100	6057 ms	143776 KiB

regions

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int MAXN = 2 * 1e5 + 10;
const int MAXR = 25000 + 10;
const int SQRT = 160;

int n, r, q;
vector<vector<int>> tree(MAXN);
int region[MAXN], cnt[MAXR];
vector<vector<int>> byRegion;

bool isHeavy[MAXR];
vector<vector<int>> calcHeavy, calcLight;

int in[MAXN], out[MAXN], timer = 0;

int cntCurrentHeavyRegion = 0; 

void dfsHeavy(int node, int par, int currentHeavyRegion)
{
    if(region[node] == currentHeavyRegion)
    {
        calcHeavy[currentHeavyRegion][currentHeavyRegion] += cntCurrentHeavyRegion;
        cntCurrentHeavyRegion++;
    }
    else
    {
        calcHeavy[currentHeavyRegion][region[node]] += cntCurrentHeavyRegion;
    }

    for(int& to : tree[node])
    {
        if(to == par) continue;
        dfsHeavy(to, node, currentHeavyRegion);
    }

    if(region[node] == currentHeavyRegion)
    {
        cntCurrentHeavyRegion--;
    }
}

void dfsLight(int node, int par)
{
    in[node] = ++timer;

    if(!isHeavy[region[node]])
    {
        calcLight[region[node]].push_back(node);
    }
    
    byRegion[region[node]].push_back(in[node]);

    for(int& to : tree[node])
    {
        if(to == par) continue;
        dfsLight(to, node);
    }

    out[node] = timer;
}

int binary(vector<int>& v, int k)
{
    int l = -1, r = v.size();

    while(r > l + 1)
    {
        int m = (l + r) / 2;

        if(v[m] >= k) r = m;
        else l = m;
    }

    return r;
}

int query(int x, int y)
{
    if(isHeavy[x])
    {
        return calcHeavy[x][y];
    }

    int answer = 0;

    for(int& child : calcLight[x])
    {
        int low = binary(byRegion[y], in[child]);
        int high = binary(byRegion[y], out[child] + 1);

        answer += high - low;
    }

    return answer;
}

void solve()
{
    cin >> n >> r >> q;

    cin >> region[1];

    cnt[region[1]]++;

    for(int i = 2 ; i <= n ; ++i)
    {
        int parent; cin >> parent >> region[i]; 

        cnt[region[i]]++;
        tree[parent].push_back(i);
        tree[i].push_back(parent);
    }

    byRegion.assign(r + 1, {});
    calcHeavy.assign(r + 1, {});  
    calcLight.resize(r + 1);

    for(int i = 1 ; i <= r ; ++i)
    {
        if(cnt[i] >= SQRT) 
        {
            isHeavy[i] = true;
            cntCurrentHeavyRegion = 0;
            calcHeavy[i].assign(r + 1, 0);

            dfsHeavy(1, 0, i);
        }
        else isHeavy[i] = false;
    }

    dfsLight(1, 0);

    for(int qq = 1 ; qq <= q ; ++qq)
    {
        int r1, r2; cin >> r1 >> r2;
        cout << query(r1, r2) << "\n"; 
    }
}

void fastIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

signed main()
{
    fastIO();
    solve();
}

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