oj.uz

Submission #871462

# Submission time Handle Problem Language Result Execution time Memory
871462 2023-11-10T22:09:48 Z Matjaz Regions (IOI09_regions) C++14
30 / 100
 3901 ms 131072 KB 
//
//  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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 8 ms 1112 KB Output is correct
7 Correct 12 ms 1368 KB Output is correct
8 Correct 16 ms 2136 KB Output is correct
9 Correct 27 ms 7000 KB Output is correct
10 Correct 56 ms 17916 KB Output is correct
11 Correct 76 ms 17800 KB Output is correct
12 Correct 94 ms 37944 KB Output is correct
13 Correct 116 ms 34612 KB Output is correct
14 Correct 142 ms 27056 KB Output is correct
15 Correct 165 ms 44844 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2639 ms 67980 KB Output is correct
2 Correct 3901 ms 77072 KB Output is correct
3 Correct 3657 ms 103792 KB Output is correct
4 Runtime error 61 ms 131072 KB Execution killed with signal 9
5 Runtime error 65 ms 131072 KB Execution killed with signal 9
6 Runtime error 69 ms 131072 KB Execution killed with signal 9
7 Runtime error 81 ms 131072 KB Execution killed with signal 9
8 Runtime error 88 ms 131072 KB Execution killed with signal 9
9 Runtime error 107 ms 131072 KB Execution killed with signal 9
10 Runtime error 118 ms 131072 KB Execution killed with signal 9
11 Runtime error 132 ms 131072 KB Execution killed with signal 9
12 Runtime error 130 ms 131072 KB Execution killed with signal 9
13 Runtime error 123 ms 131072 KB Execution killed with signal 9
14 Runtime error 140 ms 131072 KB Execution killed with signal 9
15 Runtime error 130 ms 131072 KB Execution killed with signal 9
16 Runtime error 129 ms 131072 KB Execution killed with signal 9
17 Runtime error 132 ms 131072 KB Execution killed with signal 9