oj.uz

Submission #543066

# Submission time Handle Problem Language Result Execution time Memory
543066 2022-03-29T03:44:01 Z Netr Regions (IOI09_regions) C++14
100 / 100
 3482 ms 48144 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++){
        if(regionRanges[i].empty()) continue;
        int idx = 0;
        for(int p2 : regionIds[r]){
            if(p2 < regionRanges[i][0].first) continue;
            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){
    if(regionRanges[r1].empty()) return 0;

    int res = 0, idx = 0;
    for(int p2 : regionIds[r2]){
        if(p2 < regionRanges[r1][0].first) continue;
        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;
        D("Querying %d %d\n", 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:53: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]
   53 |         while(idx < regionRanges[r].size() - 1 && regionRanges[r][idx+1].first <= i){
      |               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'void precompSecond(int, int)':
regions.cpp:67: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]
   67 |             while(idx < regionRanges[i].size() - 1 && regionRanges[i][idx+1].first <= p2){
      |                   ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'int query(int, int)':
regions.cpp:82: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]
   82 |         while(idx != regionRanges[r1].size() - 1 &&  regionRanges[r1][idx+1].first <= p2){
      |               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6352 KB Output is correct
2 Correct 4 ms 6352 KB Output is correct
3 Correct 6 ms 6352 KB Output is correct
4 Correct 6 ms 6352 KB Output is correct
5 Correct 10 ms 6480 KB Output is correct
6 Correct 23 ms 6480 KB Output is correct
7 Correct 27 ms 6484 KB Output is correct
8 Correct 30 ms 6608 KB Output is correct
9 Correct 42 ms 7248 KB Output is correct
10 Correct 74 ms 7248 KB Output is correct
11 Correct 89 ms 7752 KB Output is correct
12 Correct 100 ms 8480 KB Output is correct
13 Correct 138 ms 8528 KB Output is correct
14 Correct 154 ms 9084 KB Output is correct
15 Correct 145 ms 13440 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 13560 KB Output is correct
2 Correct 778 ms 12820 KB Output is correct
3 Correct 1189 ms 16368 KB Output is correct
4 Correct 175 ms 9092 KB Output is correct
5 Correct 269 ms 11684 KB Output is correct
6 Correct 850 ms 14344 KB Output is correct
7 Correct 1138 ms 16696 KB Output is correct
8 Correct 1613 ms 28592 KB Output is correct
9 Correct 1191 ms 20800 KB Output is correct
10 Correct 3360 ms 48144 KB Output is correct
11 Correct 1734 ms 22964 KB Output is correct
12 Correct 1564 ms 21392 KB Output is correct
13 Correct 1669 ms 22828 KB Output is correct
14 Correct 3298 ms 26028 KB Output is correct
15 Correct 3252 ms 28852 KB Output is correct
16 Correct 3160 ms 39636 KB Output is correct
17 Correct 3482 ms 41092 KB Output is correct