oj.uz

Submission #543067

# Submission time Handle Problem Language Result Execution time Memory
543067 2022-03-29T03:55:45 Z Netr Regions (IOI09_regions) C++14
0 / 100
 8000 ms 101092 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];
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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4 ms 6352 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 6352 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 6352 KB Time limit exceeded (wall clock)
4 Execution timed out 3 ms 6376 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 6424 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 6480 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 6480 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 6608 KB Time limit exceeded (wall clock)
9 Execution timed out 5 ms 7248 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 7120 KB Time limit exceeded (wall clock)
11 Execution timed out 7 ms 7504 KB Time limit exceeded (wall clock)
12 Execution timed out 9 ms 8292 KB Time limit exceeded (wall clock)
13 Execution timed out 11 ms 8272 KB Time limit exceeded (wall clock)
14 Execution timed out 23 ms 8784 KB Time limit exceeded (wall clock)
15 Execution timed out 19 ms 13016 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 333 ms 12976 KB Time limit exceeded (wall clock)
2 Execution timed out 278 ms 12224 KB Time limit exceeded (wall clock)
3 Execution timed out 302 ms 15528 KB Time limit exceeded (wall clock)
4 Execution timed out 14 ms 8784 KB Time limit exceeded (wall clock)
5 Execution timed out 16 ms 11344 KB Time limit exceeded (wall clock)
6 Execution timed out 5921 ms 59448 KB Time limit exceeded (wall clock)
7 Execution timed out 7244 ms 74240 KB Time limit exceeded (wall clock)
8 Execution timed out 8037 ms 91820 KB Time limit exceeded
9 Execution timed out 65 ms 19660 KB Time limit exceeded (wall clock)
10 Execution timed out 8028 ms 101092 KB Time limit exceeded
11 Execution timed out 85 ms 21376 KB Time limit exceeded (wall clock)
12 Execution timed out 8041 ms 21084 KB Time limit exceeded
13 Execution timed out 8045 ms 22656 KB Time limit exceeded
14 Execution timed out 8045 ms 27540 KB Time limit exceeded
15 Execution timed out 8051 ms 29048 KB Time limit exceeded
16 Execution timed out 8053 ms 40112 KB Time limit exceeded
17 Execution timed out 8029 ms 45036 KB Time limit exceeded