oj.uz

Submission #236324

# Submission time Handle Problem Language Result Execution time Memory
236324 2020-06-01T10:51:51 Z nicolaalexandra Regions (IOI09_regions) C++14
55 / 100
 8000 ms 35640 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];
pair <int,int> poz[DIM],w[DIMR];
int ans[510][DIMR];
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);
    int idx = 0;
    for (i=r;i>=max(1,r-500);i--){
        r1 = w[i].second;
        //if (v[i].size() < val)
         //   continue;
        f[r1] = ++idx;
        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;
            ans[idx][r2] = sol;
        }
    }


    /// 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 8 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 12 ms 5760 KB Output is correct
5 Correct 14 ms 5888 KB Output is correct
6 Correct 31 ms 7040 KB Output is correct
7 Correct 41 ms 6400 KB Output is correct
8 Correct 51 ms 6784 KB Output is correct
9 Correct 90 ms 7672 KB Output is correct
10 Correct 218 ms 8568 KB Output is correct
11 Correct 280 ms 7800 KB Output is correct
12 Correct 620 ms 9464 KB Output is correct
13 Correct 466 ms 8824 KB Output is correct
14 Correct 477 ms 8188 KB Output is correct
15 Correct 541 ms 10872 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1628 ms 11024 KB Output is correct
2 Correct 1738 ms 11000 KB Output is correct
3 Correct 2484 ms 13048 KB Output is correct
4 Correct 1137 ms 17308 KB Output is correct
5 Correct 1913 ms 20764 KB Output is correct
6 Correct 2543 ms 24468 KB Output is correct
7 Correct 4169 ms 31396 KB Output is correct
8 Correct 7151 ms 35640 KB Output is correct
9 Execution timed out 8045 ms 28680 KB Time limit exceeded
10 Execution timed out 8048 ms 31768 KB Time limit exceeded
11 Execution timed out 8051 ms 31760 KB Time limit exceeded
12 Execution timed out 8047 ms 26456 KB Time limit exceeded
13 Execution timed out 8031 ms 25520 KB Time limit exceeded
14 Execution timed out 8037 ms 18764 KB Time limit exceeded
15 Execution timed out 8064 ms 24972 KB Time limit exceeded
16 Execution timed out 8015 ms 32484 KB Time limit exceeded
17 Execution timed out 8028 ms 27336 KB Time limit exceeded