Submission #236341

#	Time	Username	Problem	Language	Result	Execution time	Memory
236341		nicolaalexandra	Regions (IOI09_regions)	C++14	100 / 100	3934 ms	76408 KiB

regions

#include <bits/stdc++.h>
#define DIM 200010
#define DIMR 25010
#define INF 2000000000
using namespace std;

vector <int> L[DIM],v[DIMR];
int c[DIM],f[DIM],E[DIM],up[DIM],fth[DIM];
pair <int,int> poz[DIM],w[DIMR];
int ans[510][DIMR];
int n,r,q,i,x,r1,r2,k,j;

void dfs (int nod, int tata){

    fth[nod] = tata;
    E[++k] = nod;
    v[c[nod]].push_back(nod);
    poz[nod].first = k;
    for (auto vecin : L[nod]){
        if (vecin != tata)
            dfs (vecin,nod);
    }
    poz[nod].second = k;
}



int main (){

   //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>r>>q;
    cin>>c[1];
    for (i=2;i<=n;i++){
        cin>>x>>c[i];
        L[x].push_back(i);
        L[i].push_back(x);
    }

    dfs (1,0);


    for (i=1;i<=r;i++)
        w[i] = make_pair(v[i].size(),i);

    sort (w+1,w+r+1);

    //int val = sqrt(n);
    /// up[nod][r] - cate noduri pe drumul de la radacina la nod au regiunea r

    int idx = 0;
    for (i=r;i>=max(1,r-500);i--){
        f[w[i].second] = ++idx;

        for (j=1;j<=n;j++){
            int nod = E[j];
            up[nod] = up[fth[nod]];
            if (c[nod] == w[i].second)
                up[nod]++;

            ans[idx][c[nod]] += up[nod];
        }

    }


   // dfs2 (1,0);


    /// vreau sa vad cat de prost merge asta

    for (;q--;){
        cin>>r1>>r2;

        if (f[r1]){
            cout<<ans[f[r1]][r2]<<endl;
            continue;
        }

        int sol = 0;
        for (auto it : v[r1]){

            /// cate noduri de cu regiunea r2 sunt in subarborele asta
            int x = poz[it].first, y = poz[it].second;

            int st = 0, dr = v[r2].size()-1, sol_st = INF;
            while (st <= dr){
                int mid = (st+dr)>>1;
                if (poz[v[r2][mid]].first >= x){
                    sol_st = mid;
                    dr = mid-1;
                } else st = mid+1;
            }

            st = 0, dr = v[r2].size()-1; int sol_dr = -1;
            while (st <= dr){
                int mid = (st+dr)>>1;
                if (poz[v[r2][mid]].first <= y){
                    sol_dr = mid;
                    st = mid+1;
                } else dr = mid-1;
            }

            if (sol_st <= sol_dr)
                sol += sol_dr - sol_st + 1;

        }
        cout<<sol<<endl;
    }

    return 0;
}

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