oj.uz

Submission #871466

# Submission time Handle Problem Language Result Execution time Memory
871466 2023-11-10T22:47:19 Z Matjaz Regions (IOI09_regions) C++14
85 / 100
 8000 ms 103792 KB 
//
//  IOI09Regions.cpp
//  
//
//  Created by Matjaz Leonardis on 10/11/2023.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N,R,Q;

vector<vector<int> > s;
vector<vector<int> > region_members;
vector<int> H, S;


vector<vector<int> > sum;


int time1 = 0;
vector<int> start;
vector<int> end1;

void compute_times(int x){
    start[x] = time1;
    time1++;
    for (int i=0;i<s[x].size();i++){
        compute_times(s[x][i]);
    }
    end1[x] = time1;
    time1++;
}

void compute_sums(int x) {
    for (int i=0;i<s[x].size();i++){
        compute_sums(s[x][i]);
        for (int j=0;j<R;j++) sum[x][j] += sum[s[x][i]][j];
        sum[x][H[s[x][i]]] += 1;
    }
}



int main(){
    cin >> N >> R >> Q;
    
    H.assign(N, 0);
    S.assign(N, 0);
    region_members.assign(R, vector<int>());
    
    for (int i=0;i<N;i++){
        if (i == 0) cin >> H[i]; else
            cin >> S[i] >> H[i];
        S[i]--;
        H[i]--;
        region_members[H[i]].push_back(i);
    }
    
    s.assign(N, vector<int> ());
    for (int i=1;i<N;i++) s[S[i]].push_back(i);
    
    if (R <= 500){
        
        sum.assign(N, vector<int>(R));
        compute_sums(0);
        
        for (int q=0;q<Q;q++){
            int r1,r2;
            cin >> r1 >> r2;
            r1--;r2--;
            int total = 0;
            for (int i=0;i<region_members[r1].size();i++){
                total += sum[region_members[r1][i]][r2];
            }
            cout << total << endl;
        }
    } else {
        
        start.assign(N, -1);
        end1.assign(N, -1);
        
        compute_times(0);
        
        vector<vector<int> > tmp(R, vector<int>());
        for (int i=0;i<R;i++){
            for (int j=0;j<region_members[i].size();j++) tmp[i].push_back(start[region_members[i][j]]);
            sort(tmp[i].begin(), tmp[i].end());
        }
        
        
        for (int q=0;q<Q;q++){
            int r1,r2;
            cin >> r1 >> r2;
            r1--;r2--;
            int total = 0;

            for (int i=0;i<region_members[r1].size();i++){
                
                int e1 = region_members[r1][i];
                
                int strt = lower_bound(tmp[r2].begin(), tmp[r2].end(), start[e1]) - tmp[r2].begin();
                int nd = lower_bound(tmp[r2].begin(), tmp[r2].end(), end1[e1]) - tmp[r2].begin();
                
                total += nd - strt;
                
            }
            
            cout << total << endl;
        }
    }
    
    return 0;
}

Compilation message

regions.cpp: In function 'void compute_times(int)':
regions.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i=0;i<s[x].size();i++){
      |                  ~^~~~~~~~~~~~
regions.cpp: In function 'void compute_sums(int)':
regions.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i=0;i<s[x].size();i++){
      |                  ~^~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for (int i=0;i<region_members[r1].size();i++){
      |                          ~^~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for (int j=0;j<region_members[i].size();j++) tmp[i].push_back(start[region_members[i][j]]);
      |                          ~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             for (int i=0;i<region_members[r1].size();i++){
      |                          ~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 8 ms 1112 KB Output is correct
7 Correct 12 ms 1368 KB Output is correct
8 Correct 20 ms 2136 KB Output is correct
9 Correct 29 ms 7000 KB Output is correct
10 Correct 56 ms 17924 KB Output is correct
11 Correct 78 ms 17792 KB Output is correct
12 Correct 119 ms 38012 KB Output is correct
13 Correct 120 ms 34620 KB Output is correct
14 Correct 137 ms 27064 KB Output is correct
15 Correct 184 ms 44844 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2577 ms 67984 KB Output is correct
2 Correct 4051 ms 77072 KB Output is correct
3 Correct 3895 ms 103792 KB Output is correct
4 Correct 235 ms 3044 KB Output is correct
5 Correct 262 ms 4952 KB Output is correct
6 Correct 1146 ms 5064 KB Output is correct
7 Correct 1410 ms 6752 KB Output is correct
8 Correct 1026 ms 12576 KB Output is correct
9 Correct 1844 ms 14624 KB Output is correct
10 Correct 3711 ms 20644 KB Output is correct
11 Correct 3928 ms 16288 KB Output is correct
12 Correct 5571 ms 16992 KB Output is correct
13 Correct 5906 ms 17196 KB Output is correct
14 Execution timed out 8009 ms 17228 KB Time limit exceeded
15 Execution timed out 8087 ms 21948 KB Time limit exceeded
16 Correct 6856 ms 27456 KB Output is correct
17 Execution timed out 8055 ms 25892 KB Time limit exceeded