제출 #543066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543066		Netr	Regions (IOI09_regions)	C++14	100 / 100	3482 ms	48144 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], 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();
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 85 / 85