답안 #871474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871474 2023-11-10T23:41:31 Z Matjaz Regions (IOI09_regions) C++14
100 / 100
3997 ms 52700 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> > chain; // O(R * N)
vector<vector<int> > answer;

int time1 = 0;
vector<int> start; // O(N)
vector<int> end1; // O(N)

vector<bool> isBigRegion;
vector<int> bigRegionID;
int bigRegions = 0;

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_bigregion_sums(int x) {
    if (S[x] != -1){
        chain[x] = chain[S[x]];
        if (bigRegionID[H[S[x]]] != -1) chain[x][bigRegionID[H[S[x]]]]++;
    }
    if (bigRegionID[H[x]] != -1){
        for (int i=0;i<bigRegions;i++) answer[i][bigRegionID[H[x]]] += chain[x][i];
    }
    
    for (int i=0;i<s[x].size();i++) compute_bigregion_sums(s[x][i]);
    
}



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);
    
    isBigRegion.assign(R, false);
    bigRegionID.assign(R, -1);
    for (int i=0;i<R;i++) isBigRegion[i] = region_members[i].size() > 500;
    for (int i=0;i<R;i++) if (isBigRegion[i]){
        bigRegionID[i] = bigRegions;
        bigRegions++;
    }
    
    answer.assign(bigRegions, vector<int> (bigRegions));
    chain.assign(N, vector<int> (bigRegions));
    
    compute_bigregion_sums(0);
    
    start.assign(N, -1);
    end1.assign(N, -1);
    compute_times(0);
    vector<vector<int> > tmp(R, vector<int>()); // O(N)
    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());
    }
    
    
    for (int q=0;q<Q;q++){
        int r1,r2;
        cin >> r1 >> r2;
        r1--;r2--;
        int total = 0;
        if (!isBigRegion[r1]){
            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;
                
            }
        } else if (isBigRegion[r2]){
            total = answer[bigRegionID[r1]][bigRegionID[r2]];
        } else {
            for (int i=0;i<region_members[r2].size();i++){
                int e2 = region_members[r2][i];
                total += chain[e2][bigRegionID[r1]];
            }
        }
        
        cout << total << endl;
    }
    
    return 0;
}

Compilation message

regions.cpp: In function 'void compute_times(int)':
regions.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i=0;i<s[x].size();i++){
      |                  ~^~~~~~~~~~~~
regions.cpp: In function 'void compute_bigregion_sums(int)':
regions.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i=0;i<s[x].size();i++) compute_bigregion_sums(s[x][i]);
      |                  ~^~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for (int j=0;j<region_members[i].size();j++) tmp[i].push_back(start[region_members[i][j]]);
      |                      ~^~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for (int i=0;i<region_members[r1].size();i++){
      |                          ~^~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |             for (int i=0;i<region_members[r2].size();i++){
      |                          ~^~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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 7 ms 344 KB Output is correct
7 Correct 14 ms 344 KB Output is correct
8 Correct 16 ms 600 KB Output is correct
9 Correct 27 ms 1112 KB Output is correct
10 Correct 50 ms 1476 KB Output is correct
11 Correct 85 ms 2032 KB Output is correct
12 Correct 95 ms 2796 KB Output is correct
13 Correct 131 ms 2648 KB Output is correct
14 Correct 221 ms 3536 KB Output is correct
15 Correct 182 ms 6592 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1577 ms 13564 KB Output is correct
2 Correct 1805 ms 12964 KB Output is correct
3 Correct 2372 ms 15624 KB Output is correct
4 Correct 190 ms 3828 KB Output is correct
5 Correct 255 ms 5844 KB Output is correct
6 Correct 1134 ms 6320 KB Output is correct
7 Correct 1352 ms 8432 KB Output is correct
8 Correct 1085 ms 14960 KB Output is correct
9 Correct 1816 ms 18212 KB Output is correct
10 Correct 3705 ms 24740 KB Output is correct
11 Correct 3997 ms 21092 KB Output is correct
12 Correct 1151 ms 27472 KB Output is correct
13 Correct 1572 ms 27796 KB Output is correct
14 Correct 1722 ms 41028 KB Output is correct
15 Correct 2518 ms 33088 KB Output is correct
16 Correct 2201 ms 38516 KB Output is correct
17 Correct 2136 ms 52700 KB Output is correct