oj.uz

Submission #415752

# Submission time Handle Problem Language Result Execution time Memory
415752 2021-06-01T13:01:31 Z Antekb Regions (IOI09_regions) C++14
100 / 100
 4951 ms 130604 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=500, M=25000, K=200000;
vector<int> E[K];
int R[K], pre[K], post[K], ile3[M], sta[M], sta2[M];
vector<int> pocz[M], kon[M];
int ile[M][N], ile2[M][N], gdzie[M];
vector<int> duz;
int wsk=0;
void dfs(int v){
    //cout<<v<<"q\n";
    pre[v]=wsk++;
    pocz[R[v]].push_back(pre[v]);
    sta[R[v]]++;
    sta2[R[v]]++;
    for(int i=0; i<duz.size(); i++){
        ile[R[v]][i]-=sta[duz[i]];
        ile2[R[v]][i]+=sta2[duz[i]];
    }
    for(int u:E[v]){
        dfs(u);
    }
    for(int i=0; i<duz.size(); i++){
        ile[R[v]][i]+=sta[duz[i]];
    }
    sta2[R[v]]--;
    post[v]=wsk;
    kon[R[v]].push_back(post[v]);
}
int main(){
    int n, r, q;
    cin>>n>>r>>q;
    for(int i=0; i<n ;i++){
        int h, p;
        if(i){
            cin>>p;
            p--;
            E[p].push_back(i);
        }
        cin>>R[i];
        --R[i];

        ile3[R[i]]++;
    }
    for(int i=0; i<r; i++){
        if(ile3[i]>=N){
            duz.push_back(i);
            gdzie[i]=duz.size();
        }
    }
    dfs(0);
    for(int i=0;i<q; i++){
        int r1, r2;
        cin>>r1>>r2;
        r1--;
        r2--;
        if(gdzie[r1]){
            cout<<ile2[r2][gdzie[r1]-1];
        }
        else if(gdzie[r2]){
            cout<<ile[r1][gdzie[r2]-1];
        }
        else{
                //cout<<"a";
            int ans=0;
            for(int i=0; i<pocz[r1].size(); i++){
               // cout<<"b";
                ans+=(lower_bound(pocz[r2].begin(), pocz[r2].end(), kon[r1][i])-lower_bound(pocz[r2].begin(), pocz[r2].end(), pocz[r1][i]));
            }
            cout<<ans;
        }
        cout<<endl;
    }
}

Compilation message

regions.cpp: In function 'void dfs(int)':
regions.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i=0; i<duz.size(); i++){
      |                  ~^~~~~~~~~~~
regions.cpp:23:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0; i<duz.size(); i++){
      |                  ~^~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:34:13: warning: unused variable 'h' [-Wunused-variable]
   34 |         int h, p;
      |             ^
regions.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int i=0; i<pocz[r1].size(); i++){
      |                          ~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6148 KB Output is correct
2 Correct 6 ms 6140 KB Output is correct
3 Correct 7 ms 6088 KB Output is correct
4 Correct 12 ms 6088 KB Output is correct
5 Correct 14 ms 6216 KB Output is correct
6 Correct 21 ms 6216 KB Output is correct
7 Correct 33 ms 6204 KB Output is correct
8 Correct 35 ms 6216 KB Output is correct
9 Correct 63 ms 6784 KB Output is correct
10 Correct 130 ms 6676 KB Output is correct
11 Correct 182 ms 6984 KB Output is correct
12 Correct 216 ms 7624 KB Output is correct
13 Correct 268 ms 7152 KB Output is correct
14 Correct 365 ms 7744 KB Output is correct
15 Correct 302 ms 11584 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1698 ms 12084 KB Output is correct
2 Correct 1388 ms 10640 KB Output is correct
3 Correct 2406 ms 14784 KB Output is correct
4 Correct 265 ms 7988 KB Output is correct
5 Correct 459 ms 10268 KB Output is correct
6 Correct 1249 ms 36372 KB Output is correct
7 Correct 1730 ms 10428 KB Output is correct
8 Correct 1525 ms 56464 KB Output is correct
9 Correct 2066 ms 16404 KB Output is correct
10 Correct 4610 ms 23564 KB Output is correct
11 Correct 4951 ms 15908 KB Output is correct
12 Correct 1425 ms 78880 KB Output is correct
13 Correct 2214 ms 79512 KB Output is correct
14 Correct 2747 ms 94184 KB Output is correct
15 Correct 4054 ms 121656 KB Output is correct
16 Correct 3768 ms 130604 KB Output is correct
17 Correct 3716 ms 107900 KB Output is correct