Submission #871471

#	Time	Username	Problem	Language	Result	Execution time	Memory
871471		Matjaz	Regions (IOI09_regions)	C++14	55 / 100	3873 ms	106464 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> > chain; // O(R * N)
vector<vector<int> > answer;

int time1 = 0;
vector<int> start; // O(N)
vector<int> end1; // O(N)

vector<bool> isBigRegion;
vector<int> bigRegionID;
int bigRegions = 0;

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_bigregion_sums(int x) {
    if (S[x] != -1){
        chain[x] = chain[S[x]];
        if (bigRegionID[H[S[x]]] != -1) chain[x][bigRegionID[H[S[x]]]]++;
    }
    if (bigRegionID[H[x]] != -1){
        for (int i=0;i<bigRegions;i++) answer[i][H[x]] += chain[x][i];
    }
    
    for (int i=0;i<s[x].size();i++) compute_bigregion_sums(s[x][i]);
    
}



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);
    
    isBigRegion.assign(R, false);
    bigRegionID.assign(R, -1);
    for (int i=0;i<R;i++) isBigRegion[i] = region_members[i].size() > 500;
    for (int i=0;i<R;i++) if (isBigRegion[i]){
        bigRegionID[i] = bigRegions;
        bigRegions++;
    }
    
    answer.assign(bigRegions, vector<int> (bigRegions));
    chain.assign(N, vector<int> (bigRegions));
    
    compute_bigregion_sums(0);
    
    start.assign(N, -1);
    end1.assign(N, -1);
    compute_times(0);
    vector<vector<int> > tmp(R, vector<int>()); // O(N)
    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;
        if (!isBigRegion[r1]){
            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;
                
            }
        } else if (isBigRegion[r2]){
            total = answer[r1][r2];
        } else {
            for (int i=0;i<region_members[r2].size();i++){
                int e2 = region_members[r2][i];
                total += chain[e2][bigRegionID[r1]];
            }
        }
        
        cout << total << endl;
    }
    
    return 0;
}

Compilation message (stderr)

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

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