oj.uz

Submission #543061

# Submission time Handle Problem Language Result Execution time Memory
543061 2022-03-29T03:11:20 Z Netr Regions (IOI09_regions) C++14
0 / 100
 1075 ms 79608 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){
    D("Precomping %d first\n", r);
    int idx = 0;
    if(regionRanges[r].empty()) return;
    for(int i = regionRanges[r][0].first; i < N; i++){
        D("i: %d, ", i);
        while(idx < regionRanges[r].size() - 1 && regionRanges[r][idx+1].first <= i){
            idx++;
        }
        D("Region range: %d %d\n", regionRanges[r][idx].first, regionRanges[r][idx].second);
        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 j = 0; j < regionIds[r].size(); j++){
            while(idx < regionRanges[i].size() - 1 && regionRanges[i][idx+1].first <= regionIds[r][j]){
                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 i = 0; i < regionIds[r2].size(); i++){
        while(idx < regionRanges[r1].size() - 1 && regionRanges[r1][idx+1].first <= regionIds[r2][i]){
            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:51: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]
   51 |         while(idx < regionRanges[r].size() - 1 && regionRanges[r][idx+1].first <= i){
      |               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'void precompSecond(int, int)':
regions.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int j = 0; j < regionIds[r].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:63: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]
   63 |             while(idx < regionRanges[i].size() - 1 && regionRanges[i][idx+1].first <= regionIds[r][j]){
      |                   ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'int query(int, int)':
regions.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0; i < regionIds[r2].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:75: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]
   75 |         while(idx < regionRanges[r1].size() - 1 && regionRanges[r1][idx+1].first <= regionIds[r2][i]){
      |               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 12892 KB Execution killed with signal 11
2 Runtime error 12 ms 12788 KB Execution killed with signal 11
3 Runtime error 11 ms 12796 KB Execution killed with signal 11
4 Incorrect 8 ms 6480 KB Output isn't correct
5 Incorrect 9 ms 6480 KB Output isn't correct
6 Runtime error 12 ms 13064 KB Execution killed with signal 11
7 Incorrect 18 ms 6480 KB Output isn't correct
8 Incorrect 19 ms 6608 KB Output isn't correct
9 Incorrect 43 ms 7248 KB Output isn't correct
10 Incorrect 65 ms 7248 KB Output isn't correct
11 Incorrect 95 ms 7684 KB Output isn't correct
12 Incorrect 122 ms 8480 KB Output isn't correct
13 Incorrect 142 ms 8500 KB Output isn't correct
14 Incorrect 143 ms 9084 KB Output isn't correct
15 Incorrect 215 ms 13424 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 661 ms 13564 KB Output isn't correct
2 Incorrect 741 ms 12816 KB Output isn't correct
3 Incorrect 1075 ms 16372 KB Output isn't correct
4 Runtime error 33 ms 18216 KB Execution killed with signal 11
5 Runtime error 36 ms 23524 KB Execution killed with signal 11
6 Runtime error 39 ms 21960 KB Execution killed with signal 11
7 Runtime error 45 ms 25216 KB Execution killed with signal 11
8 Runtime error 76 ms 41248 KB Execution killed with signal 11
9 Runtime error 98 ms 41920 KB Execution killed with signal 11
10 Runtime error 110 ms 56932 KB Execution killed with signal 11
11 Runtime error 136 ms 46324 KB Execution killed with signal 11
12 Runtime error 120 ms 42708 KB Execution killed with signal 11
13 Runtime error 105 ms 45776 KB Execution killed with signal 11
14 Runtime error 118 ms 45600 KB Execution killed with signal 11
15 Runtime error 521 ms 57916 KB Execution killed with signal 11
16 Runtime error 135 ms 79608 KB Execution killed with signal 11
17 Runtime error 143 ms 75780 KB Execution killed with signal 11