oj.uz

Submission #871465

# Submission time Handle Problem Language Result Execution time Memory
871465 2023-11-10T22:33:30 Z Matjaz Regions (IOI09_regions) C++14
70 / 100
 8000 ms 103792 KB 
//
//  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;


vector<vector<int> > sum;


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);
    
    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 {
        
        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

regions.cpp: In function 'void compute_times(int)':
regions.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int i=0;i<s[x].size();i++){
      |                  ~^~~~~~~~~~~~
regions.cpp: In function 'void compute_sums(int)':
regions.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i=0;i<s[x].size();i++){
      |                  ~^~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for (int i=0;i<region_members[r1].size();i++){
      |                          ~^~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:95:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             for(int i=0;i<region_members[r2].size();i++) tmp.push_back(start[region_members[r2][i]]);
      |                         ~^~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             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 1 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 356 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 9 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 24 ms 7000 KB Output is correct
10 Correct 58 ms 18096 KB Output is correct
11 Correct 71 ms 17808 KB Output is correct
12 Correct 97 ms 37948 KB Output is correct
13 Correct 120 ms 34632 KB Output is correct
14 Correct 131 ms 27064 KB Output is correct
15 Correct 169 ms 44860 KB Output is correct

Subtask #2
55.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2470 ms 67984 KB Output is correct
2 Correct 3709 ms 77072 KB Output is correct
3 Correct 3622 ms 103792 KB Output is correct
4 Correct 225 ms 2792 KB Output is correct
5 Correct 291 ms 4624 KB Output is correct
6 Correct 1508 ms 4556 KB Output is correct
7 Correct 1826 ms 6188 KB Output is correct
8 Correct 1377 ms 11636 KB Output is correct
9 Correct 2562 ms 13092 KB Output is correct
10 Correct 4714 ms 18632 KB Output is correct
11 Correct 5067 ms 14156 KB Output is correct
12 Execution timed out 8051 ms 15580 KB Time limit exceeded
13 Execution timed out 8077 ms 15776 KB Time limit exceeded
14 Execution timed out 8063 ms 16948 KB Time limit exceeded
15 Execution timed out 8061 ms 20924 KB Time limit exceeded
16 Execution timed out 8073 ms 25816 KB Time limit exceeded
17 Execution timed out 8042 ms 24152 KB Time limit exceeded