oj.uz

Submission #236323

# Submission time Handle Problem Language Result Execution time Memory
236323 2020-06-01T10:46:18 Z nicolaalexandra Regions (IOI09_regions) C++14
30 / 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 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 9 ms 9728 KB Output is correct
3 Correct 12 ms 9728 KB Output is correct
4 Correct 14 ms 9856 KB Output is correct
5 Correct 15 ms 9856 KB Output is correct
6 Correct 43 ms 13696 KB Output is correct
7 Correct 53 ms 11264 KB Output is correct
8 Correct 61 ms 12288 KB Output is correct
9 Correct 117 ms 15864 KB Output is correct
10 Correct 300 ms 21240 KB Output is correct
11 Correct 323 ms 15096 KB Output is correct
12 Correct 700 ms 23780 KB Output is correct
13 Correct 587 ms 18168 KB Output is correct
14 Correct 596 ms 13816 KB Output is correct
15 Correct 558 ms 17148 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1856 ms 16504 KB Output is correct
2 Correct 1875 ms 16884 KB Output is correct
3 Correct 2628 ms 19928 KB Output is correct
4 Runtime error 1517 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 1949 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 2462 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 3595 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 5239 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 6213 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 5842 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 4854 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 7427 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 7960 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Execution timed out 8042 ms 47608 KB Time limit exceeded
15 Execution timed out 8106 ms 90800 KB Time limit exceeded
16 Execution timed out 8050 ms 121896 KB Time limit exceeded
17 Execution timed out 8095 ms 62164 KB Time limit exceeded