Submission #871466

#	Time	Username	Problem	Language	Result	Execution time	Memory
871466		Matjaz	Regions (IOI09_regions)	C++14	85 / 100	8087 ms	103792 KiB

regions

//
//  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 (stderr)

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 / 15
• Subtask 2: 70 / 85