oj.uz

Submission #871467

# Submission time Handle Problem Language Result Execution time Memory
871467 2023-11-10T22:55:23 Z Matjaz Regions (IOI09_regions) C++14
85 / 100
 8000 ms 104936 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; // O(N)
vector<vector<int> > region_members; //O(N)
vector<int> H, S; // O(N)


vector<vector<int> > sum; // O(R * N)

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);
    
    start.assign(N, -1);
    end1.assign(N, -1);
    
    compute_times(0);
    
    vector<vector<int> > tmp(R, vector<int>());
    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());
    }
    
    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 {
        
        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++){
                
                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;
                
            }
            
            cout << total << endl;
        }
    }
    
    return 0;
}

Compilation message

regions.cpp: In function 'void compute_times(int)':
regions.cpp:30:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i=0;i<s[x].size();i++){
      |                  ~^~~~~~~~~~~~
regions.cpp: In function 'void compute_sums(int)':
regions.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i=0;i<s[x].size();i++){
      |                  ~^~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int j=0;j<region_members[i].size();j++) tmp[i].push_back(start[region_members[i][j]]);
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:86:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |             for (int i=0;i<region_members[r1].size();i++){
      |                          ~^~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             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 9 ms 1368 KB Output is correct
7 Correct 17 ms 1368 KB Output is correct
8 Correct 18 ms 2136 KB Output is correct
9 Correct 40 ms 7000 KB Output is correct
10 Correct 57 ms 18084 KB Output is correct
11 Correct 74 ms 18008 KB Output is correct
12 Correct 112 ms 38236 KB Output is correct
13 Correct 129 ms 35112 KB Output is correct
14 Correct 162 ms 27756 KB Output is correct
15 Correct 176 ms 45416 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2611 ms 68956 KB Output is correct
2 Correct 4025 ms 78124 KB Output is correct
3 Correct 3911 ms 104936 KB Output is correct
4 Correct 206 ms 3020 KB Output is correct
5 Correct 283 ms 4964 KB Output is correct
6 Correct 1109 ms 5064 KB Output is correct
7 Correct 1441 ms 6748 KB Output is correct
8 Correct 1033 ms 12572 KB Output is correct
9 Correct 1812 ms 14620 KB Output is correct
10 Correct 3834 ms 20648 KB Output is correct
11 Correct 3881 ms 16284 KB Output is correct
12 Correct 5484 ms 16992 KB Output is correct
13 Correct 5888 ms 17192 KB Output is correct
14 Execution timed out 8018 ms 17392 KB Time limit exceeded
15 Execution timed out 8063 ms 21948 KB Time limit exceeded
16 Correct 7623 ms 27456 KB Output is correct
17 Execution timed out 8025 ms 25908 KB Time limit exceeded