Submission #236323

#	Time	Username	Problem	Language	Result	Execution time	Memory
236323		nicolaalexandra	Regions (IOI09_regions)	C++14	30 / 100	8106 ms	131076 KiB

regions

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

vector <int> L[DIM],v[DIM];
int c[DIM],f[DIM];
pair <int,int> poz[DIM],w[DIM];
map <pair<int,int>,int> mp;
int n,r,q,i,x,r1,r2,k;

void dfs (int nod, int tata){
    //E[++k] = nod;
    k++;
    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);

    for (i=r;i>=max(1,r-500);i--){
        r1 = w[i].second;
        //if (v[i].size() < val)
         //   continue;
        f[r1] = 1;
        for (r2=1;r2<=r;r2++){

            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;
            }

            mp[make_pair(r1,r2)] = sol;

        }
    }


    /// vreau sa vad cat de prost merge asta

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

        if (f[r1]){
            cout<<mp[make_pair(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: 15 / 85