oj.uz

Submission #871464

# Submission time Handle Problem Language Result Execution time Memory
871464 2023-11-10T22:27:53 Z Matjaz Regions (IOI09_regions) C++14
55 / 100
 8000 ms 25784 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;


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

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.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 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 11 ms 344 KB Output is correct
7 Correct 18 ms 344 KB Output is correct
8 Correct 18 ms 344 KB Output is correct
9 Correct 29 ms 856 KB Output is correct
10 Correct 53 ms 1268 KB Output is correct
11 Correct 91 ms 1384 KB Output is correct
12 Correct 131 ms 1964 KB Output is correct
13 Correct 166 ms 1756 KB Output is correct
14 Correct 268 ms 2596 KB Output is correct
15 Correct 248 ms 5412 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8010 ms 6696 KB Time limit exceeded
2 Execution timed out 8013 ms 5680 KB Time limit exceeded
3 Execution timed out 8009 ms 8952 KB Time limit exceeded
4 Correct 229 ms 2788 KB Output is correct
5 Correct 269 ms 4616 KB Output is correct
6 Correct 1501 ms 4552 KB Output is correct
7 Correct 1878 ms 5988 KB Output is correct
8 Correct 1392 ms 11640 KB Output is correct
9 Correct 2445 ms 13080 KB Output is correct
10 Correct 4815 ms 18628 KB Output is correct
11 Correct 5083 ms 14160 KB Output is correct
12 Execution timed out 8016 ms 15576 KB Time limit exceeded
13 Execution timed out 8004 ms 15776 KB Time limit exceeded
14 Execution timed out 8084 ms 16824 KB Time limit exceeded
15 Execution timed out 8087 ms 20928 KB Time limit exceeded
16 Execution timed out 8067 ms 25784 KB Time limit exceeded
17 Execution timed out 8029 ms 24156 KB Time limit exceeded