oj.uz

Submission #236321

# Submission time Handle Problem Language Result Execution time Memory
236321 2020-06-01T10:28:43 Z nicolaalexandra Regions (IOI09_regions) C++14
75 / 100
 8000 ms 131076 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 14 ms 9728 KB Output is correct
4 Correct 14 ms 9728 KB Output is correct
5 Correct 18 ms 9728 KB Output is correct
6 Correct 29 ms 9856 KB Output is correct
7 Correct 35 ms 9856 KB Output is correct
8 Correct 43 ms 9856 KB Output is correct
9 Correct 61 ms 10240 KB Output is correct
10 Correct 99 ms 10240 KB Output is correct
11 Correct 136 ms 10616 KB Output is correct
12 Correct 162 ms 11136 KB Output is correct
13 Correct 189 ms 11008 KB Output is correct
14 Correct 299 ms 11384 KB Output is correct
15 Correct 310 ms 13692 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2470 ms 14676 KB Output is correct
2 Correct 2711 ms 14200 KB Output is correct
3 Correct 3608 ms 16376 KB Output is correct
4 Correct 293 ms 11516 KB Output is correct
5 Correct 405 ms 12920 KB Output is correct
6 Correct 2581 ms 39416 KB Output is correct
7 Correct 3478 ms 45320 KB Output is correct
8 Correct 5307 ms 81312 KB Output is correct
9 Correct 2552 ms 18912 KB Output is correct
10 Runtime error 5781 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Correct 4500 ms 21232 KB Output is correct
12 Correct 5252 ms 22116 KB Output is correct
13 Correct 5826 ms 22776 KB Output is correct
14 Execution timed out 8084 ms 44212 KB Time limit exceeded
15 Execution timed out 8016 ms 27428 KB Time limit exceeded
16 Execution timed out 8016 ms 32900 KB Time limit exceeded
17 Execution timed out 8068 ms 54512 KB Time limit exceeded