Submission #871467

#	Time	Username	Problem	Language	Result	Execution time	Memory
871467		Matjaz	Regions (IOI09_regions)	C++14	85 / 100	8063 ms	104936 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; // O(N)
vector<vector<int> > region_members; //O(N)
vector<int> H, S; // O(N)


vector<vector<int> > sum; // O(R * N)

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);
    
    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());
    }
    
    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 {
        
        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:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i=0;i<s[x].size();i++){
      |                  ~^~~~~~~~~~~~
regions.cpp: In function 'void compute_sums(int)':
regions.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i=0;i<s[x].size();i++){
      |                  ~^~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int j=0;j<region_members[i].size();j++) tmp[i].push_back(start[region_members[i][j]]);
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:86:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             for (int i=0;i<region_members[r1].size();i++){
      |                          ~^~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             for (int i=0;i<region_members[r1].size();i++){
      |                          ~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 70 / 85