Submission #236321

#	Time	Username	Problem	Language	Result	Execution time	Memory
236321		nicolaalexandra	Regions (IOI09_regions)	C++14	75 / 100	8084 ms	131076 KiB

regions

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

vector <int> L[DIM],v[DIM];
int E[DIM],c[DIM];
pair <int,int> poz[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;
    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<=k;i++){
        int nod = E[i];
        v[c[nod]].push_back(nod);
    }

    int val = sqrt(n);

    for (i=1;i<=r;i++){
        if (v[i].size() < val)
            continue;

        for (r2=1;r2<=r;r2++){

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

                /// 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(i,r2)] = sol;

        }
    }


    /// vreau sa vad cat de prost merge asta

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

        if (v[r1].size() >= val){
            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;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:44:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (v[i].size() < val)
             ~~~~~~~~~~~~^~~~~
regions.cpp:88:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (v[r1].size() >= val){
             ~~~~~~~~~~~~~^~~~~~

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