oj.uz

Submission #543060

# Submission time Handle Problem Language Result Execution time Memory
543060 2022-03-29T03:10:21 Z Netr Regions (IOI09_regions) C++14
0 / 100
 1316 ms 79572 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);

    for(auto i : regionRanges[3]){
        D("%d %d\n", i.first, i.second);
    }

    // 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]){
      |               ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:97:14: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   97 |     for(auto i : regionRanges[3]){
      |              ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 12852 KB Execution killed with signal 11
2 Runtime error 11 ms 12880 KB Execution killed with signal 11
3 Runtime error 12 ms 12844 KB Execution killed with signal 11
4 Incorrect 7 ms 6352 KB Output isn't correct
5 Incorrect 9 ms 6496 KB Output isn't correct
6 Runtime error 12 ms 13096 KB Execution killed with signal 11
7 Incorrect 34 ms 6480 KB Output isn't correct
8 Incorrect 37 ms 6596 KB Output isn't correct
9 Incorrect 47 ms 7248 KB Output isn't correct
10 Incorrect 75 ms 7204 KB Output isn't correct
11 Incorrect 99 ms 7692 KB Output isn't correct
12 Incorrect 115 ms 8484 KB Output isn't correct
13 Incorrect 130 ms 8540 KB Output isn't correct
14 Incorrect 186 ms 8972 KB Output isn't correct
15 Incorrect 206 ms 13420 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 678 ms 13560 KB Output isn't correct
2 Incorrect 952 ms 12808 KB Output isn't correct
3 Incorrect 1316 ms 16372 KB Output isn't correct
4 Runtime error 25 ms 18196 KB Execution killed with signal 11
5 Runtime error 32 ms 23488 KB Execution killed with signal 11
6 Runtime error 46 ms 21996 KB Execution killed with signal 11
7 Runtime error 46 ms 25264 KB Execution killed with signal 11
8 Runtime error 72 ms 41320 KB Execution killed with signal 11
9 Runtime error 98 ms 41996 KB Execution killed with signal 11
10 Runtime error 99 ms 56876 KB Execution killed with signal 11
11 Runtime error 125 ms 46328 KB Execution killed with signal 11
12 Runtime error 108 ms 42636 KB Execution killed with signal 11
13 Runtime error 100 ms 45760 KB Execution killed with signal 11
14 Runtime error 123 ms 45668 KB Execution killed with signal 11
15 Runtime error 485 ms 57828 KB Execution killed with signal 11
16 Runtime error 145 ms 79572 KB Execution killed with signal 11
17 Runtime error 127 ms 75720 KB Execution killed with signal 11