Submission #871462

#	Time	Username	Problem	Language	Result	Execution time	Memory
871462		Matjaz	Regions (IOI09_regions)	C++14	30 / 100	3901 ms	131072 KiB

regions

//
//  IOI09Regions.cpp
//  
//
//  Created by Matjaz Leonardis on 10/11/2023.
//

#include <iostream>
#include <vector>

using namespace std;

int N,R,Q;

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


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> ());
    sum.assign(N, vector<int>(R));
    
    for (int i=1;i<N;i++) s[S[i]].push_back(i);
    
    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;
    }
    
    
    
    
    return 0;
}

Compilation message (stderr)

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

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