Submission #871464

#	Time	Username	Problem	Language	Result	Execution time	Memory
871464		Matjaz	Regions (IOI09_regions)	C++14	55 / 100	8087 ms	25784 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;


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++;
}



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);
    
    for (int q=0;q<Q;q++){
        int r1,r2;
        cin >> r1 >> r2;
        r1--;r2--;
        int total = 0;
        
        vector<int> tmp;
        for(int i=0;i<region_members[r2].size();i++) tmp.push_back(start[region_members[r2][i]]);
        sort(tmp.begin(), tmp.end());
        for (int i=0;i<region_members[r1].size();i++){
            
            int e1 = region_members[r1][i];
            
            int strt = lower_bound(tmp.begin(), tmp.end(), start[e1]) - tmp.begin();
            int nd = lower_bound(tmp.begin(), tmp.end(), end1[e1]) - tmp.begin();
            
            total += nd - strt;
            
        }
        
        cout << total << endl;
    }
    
    
    
    
    return 0;
}

Compilation message (stderr)

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

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