Submission #543067

#	Time	Username	Problem	Language	Result	Execution time	Memory
543067		Netr	Regions (IOI09_regions)	C++14	0 / 100	8053 ms	101092 KiB

regions

#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];
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;
    timer++;
    regionDepth[regions[n]]++;
    regionRanges[regions[n]].push_back({timer-1, regionDepth[regions[n]]});
    regionIds[regions[n]].push_back(timer-1);

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

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

// Precomputation
map<pi,int> precomp;
void precompFirst(int r){

    // 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[{r, regions[tour[i]]}] += regionRanges[r][idx].second;
    }
}

void precompSecond(int r){
    for(int i = 1; i <= R; i++){
        precomp[{i,r}] = 0;
        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[{i, r}] += 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
    for(int i = 1; i <= R; i++){
        if(regionIds[i].size() >= N/sqrt(N)){
            precompFirst(i);
            precompSecond(i);
        }
    }

    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[{r1, r2}] << "\n";
            continue;
        }
        if(regionIds[r2].size() >= N/sqrt(N)){
            D("Precomp r2\n");
            cout << precomp[{r1, r2}] << "\n";
            continue;
        }
        cout << query(r1, r2) << "\n";
    }
}

Compilation message (stderr)

regions.cpp: In function 'void precompFirst(int)':
regions.cpp:52: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]
   52 |         while(idx < regionRanges[r].size() - 1 && regionRanges[r][idx+1].first <= i){
      |               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'void precompSecond(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: 0 / 15
• Subtask 2: 0 / 85