답안 #871473

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871473 2023-11-10T23:39:49 Z Matjaz Regions (IOI09_regions) C++14
70 / 100
3765 ms 106460 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[r1][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 10 ms 344 KB Output is correct
7 Correct 12 ms 600 KB Output is correct
8 Correct 17 ms 600 KB Output is correct
9 Correct 27 ms 1112 KB Output is correct
10 Correct 45 ms 1464 KB Output is correct
11 Correct 78 ms 2016 KB Output is correct
12 Correct 100 ms 2788 KB Output is correct
13 Correct 133 ms 2648 KB Output is correct
14 Correct 209 ms 3540 KB Output is correct
15 Correct 202 ms 6596 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 53 ms 27040 KB Execution killed with signal 11
2 Runtime error 57 ms 25760 KB Execution killed with signal 11
3 Runtime error 69 ms 31452 KB Execution killed with signal 11
4 Correct 188 ms 3832 KB Output is correct
5 Correct 248 ms 5848 KB Output is correct
6 Correct 1071 ms 6324 KB Output is correct
7 Correct 1344 ms 8444 KB Output is correct
8 Correct 981 ms 14964 KB Output is correct
9 Correct 1783 ms 18208 KB Output is correct
10 Correct 3648 ms 25016 KB Output is correct
11 Correct 3765 ms 21084 KB Output is correct
12 Correct 1082 ms 27468 KB Output is correct
13 Correct 1488 ms 27672 KB Output is correct
14 Runtime error 197 ms 82752 KB Execution killed with signal 11
15 Runtime error 454 ms 66628 KB Execution killed with signal 11
16 Correct 2235 ms 38504 KB Output is correct
17 Runtime error 194 ms 106460 KB Execution killed with signal 11