oj.uz

Submission #543064

# Submission time Handle Problem Language Result Execution time Memory
543064 2022-03-29T03:29:40 Z Netr Regions (IOI09_regions) C++14
0 / 100
 1232 ms 79632 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

#ifdef DEBUG
#define D(x...) printf(x);
#else
#define D(x...)
#endif

#define lsb(x) (x&(-x))
#define g(i,x) get<i>(x)

const int MAXN = 2e5 + 5;
const int MAXR = 3e4 + 5;

int N, R, Q, regions[MAXN], tour[MAXN], tme[MAXN][2];
vector<int> adj[MAXN];
vector<pair<int, int>> regionRanges[MAXR];
vector<int> regionIds[MAXR];
int regionDepth[MAXR];

// Euler tour
int timer = 0;
void dfs(int n, int p = 1){
    tour[timer] = n;
    tme[n][0] = timer++;
    regionDepth[regions[n]]++;
    regionRanges[regions[n]].push_back({tme[n][0], regionDepth[regions[n]]});
    regionIds[regions[n]].push_back(tme[n][0]);

    for(int e : adj[n]){
        if(e == p) continue;
        dfs(e, n);
    }

    regionDepth[regions[n]]--;
    tme[n][1] = timer;
    regionRanges[regions[n]].push_back({tme[n][1], regionDepth[regions[n]]});
}

// Precomputation
int rtp[MAXR], precomp[500][MAXR][2];
void precompFirst(int r, int p){

    // if no nodes have region r, immediately return
    if(regionRanges[r].empty()) return;


    int idx = 0;
    for(int i = regionRanges[r][0].first; i < N; i++){

        while(idx < regionRanges[r].size() - 1 && regionRanges[r][idx+1].first <= i){
            idx++;
        }

        precomp[p][regions[tour[i]]][0] += regionRanges[r][idx].second;
    }
}

void precompSecond(int r, int p){
    for(int i = 1; i <= R; i++){
        int idx = 0;
        for(int p2 : regionIds[r]){
            while(idx < regionRanges[i].size() - 1 && regionRanges[i][idx+1].first <= p2){
                idx++;
            }
            precomp[p][i][1] += regionRanges[i][idx].second;
        }
    }
}

// Non-precomputed query
int query(int r1, int r2){
    int res = 0, idx = 0;

    for(int p2 : regionIds[r2]){
        while(idx != regionRanges[r1].size() - 1 &&  regionRanges[r1][idx+1].first <= p2){
            idx++;
        }
        res += regionRanges[r1][idx].second;
    }

    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> R >> Q >> regions[1];

    for(int i = 2; i <= N; i++){
        int sk, hk;
        cin >> sk >> hk;
        adj[sk].push_back(i);
        adj[i].push_back(sk);
        regions[i] = hk;
    }

    dfs(1);

    // Precompute largest
    int idx = 0;
    for(int i = 1; i <= R; i++){
        if(regionIds[i].size() >= N/sqrt(N)){
            rtp[i] = idx;
            precompFirst(i, idx);
            precompSecond(i, idx);
            idx++;
        }
    }

    for(int z = 0; z < Q; z++){
        int r1, r2;
        cin >> r1 >> r2;
        if(regionIds[r1].size() >= N/sqrt(N)){
            D("Precomp r1\n");
            cout << precomp[rtp[r1]][r2][0] << "\n";
            cout.flush();
            continue;
        }
        if(regionIds[r2].size() >= N/sqrt(N)){
            D("Precomp r2\n");
            cout << precomp[rtp[r2]][r1][1] << "\n";
            cout.flush();
            continue;
        }
        cout << query(r1, r2) << "\n";
        cout.flush();
    }
}

Compilation message

regions.cpp: In function 'void precompFirst(int, int)':
regions.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         while(idx < regionRanges[r].size() - 1 && regionRanges[r][idx+1].first <= i){
      |               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'void precompSecond(int, int)':
regions.cpp:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             while(idx < regionRanges[i].size() - 1 && regionRanges[i][idx+1].first <= p2){
      |                   ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'int query(int, int)':
regions.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         while(idx != regionRanges[r1].size() - 1 &&  regionRanges[r1][idx+1].first <= p2){
      |               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 12860 KB Execution killed with signal 11
2 Runtime error 13 ms 12788 KB Execution killed with signal 11
3 Runtime error 11 ms 12880 KB Execution killed with signal 11
4 Incorrect 5 ms 6352 KB Output isn't correct
5 Incorrect 10 ms 6480 KB Output isn't correct
6 Runtime error 11 ms 13064 KB Execution killed with signal 11
7 Incorrect 28 ms 6480 KB Output isn't correct
8 Incorrect 31 ms 6608 KB Output isn't correct
9 Incorrect 44 ms 7248 KB Output isn't correct
10 Incorrect 67 ms 7248 KB Output isn't correct
11 Incorrect 65 ms 7676 KB Output isn't correct
12 Incorrect 103 ms 8420 KB Output isn't correct
13 Incorrect 132 ms 8528 KB Output isn't correct
14 Incorrect 154 ms 9088 KB Output isn't correct
15 Incorrect 189 ms 13424 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 527 ms 13576 KB Output isn't correct
2 Incorrect 843 ms 12892 KB Output isn't correct
3 Incorrect 1232 ms 16376 KB Output isn't correct
4 Runtime error 27 ms 18192 KB Execution killed with signal 11
5 Runtime error 31 ms 23428 KB Execution killed with signal 11
6 Runtime error 42 ms 22016 KB Execution killed with signal 11
7 Runtime error 46 ms 25272 KB Execution killed with signal 11
8 Runtime error 66 ms 41288 KB Execution killed with signal 11
9 Runtime error 86 ms 41924 KB Execution killed with signal 11
10 Runtime error 113 ms 56968 KB Execution killed with signal 11
11 Runtime error 104 ms 46316 KB Execution killed with signal 11
12 Runtime error 108 ms 42692 KB Execution killed with signal 11
13 Runtime error 102 ms 45776 KB Execution killed with signal 11
14 Runtime error 114 ms 45580 KB Execution killed with signal 11
15 Runtime error 387 ms 57912 KB Execution killed with signal 11
16 Runtime error 133 ms 79632 KB Execution killed with signal 11
17 Runtime error 116 ms 75700 KB Execution killed with signal 11