oj.uz

Submission #236341

# Submission time Handle Problem Language Result Execution time Memory
236341 2020-06-01T12:05:40 Z nicolaalexandra Regions (IOI09_regions) C++14
100 / 100
 3934 ms 76408 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5632 KB Output is correct
2 Correct 7 ms 5632 KB Output is correct
3 Correct 9 ms 5760 KB Output is correct
4 Correct 13 ms 5760 KB Output is correct
5 Correct 17 ms 5888 KB Output is correct
6 Correct 33 ms 7040 KB Output is correct
7 Correct 36 ms 6528 KB Output is correct
8 Correct 44 ms 6784 KB Output is correct
9 Correct 65 ms 7800 KB Output is correct
10 Correct 123 ms 8696 KB Output is correct
11 Correct 142 ms 8056 KB Output is correct
12 Correct 188 ms 9720 KB Output is correct
13 Correct 235 ms 9160 KB Output is correct
14 Correct 216 ms 8568 KB Output is correct
15 Correct 254 ms 11256 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 860 ms 12024 KB Output is correct
2 Correct 999 ms 11768 KB Output is correct
3 Correct 1370 ms 14128 KB Output is correct
4 Correct 389 ms 17656 KB Output is correct
5 Correct 592 ms 21112 KB Output is correct
6 Correct 745 ms 24952 KB Output is correct
7 Correct 1083 ms 32104 KB Output is correct
8 Correct 1339 ms 36984 KB Output is correct
9 Correct 2328 ms 47596 KB Output is correct
10 Correct 2748 ms 70008 KB Output is correct
11 Correct 3934 ms 67924 KB Output is correct
12 Correct 2413 ms 51036 KB Output is correct
13 Correct 2161 ms 52104 KB Output is correct
14 Correct 2880 ms 60024 KB Output is correct
15 Correct 2884 ms 70852 KB Output is correct
16 Correct 2796 ms 76408 KB Output is correct
17 Correct 2851 ms 67372 KB Output is correct