oj.uz

Submission #1087940

# Submission time Handle Problem Language Result Execution time Memory
1087940 2024-09-13T14:55:09 Z Zero_OP Regions (IOI09_regions) C++14
100 / 100
 3749 ms 78972 KB 
#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(v) "[" #v " = " << (v) << "]"
#define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define rep(i, l, r) for(int i = (l); i < (r); ++i)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using ld = long double;

template<typename T> 
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }  return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){    
        if(a < b){
            return a = b, true;
        } return false;
    }

template<int dimension, typename T>
struct tensor : public vector<tensor<dimension - 1, T>> {
    static_assert(dimension > 0, "Dimension must be positive !\n");
    template<typename... Args>
    tensor(int n = 0, Args... args) : vector<tensor<dimension - 1, T>> (n, tensor<dimension - 1, T>(args...)) {}
};
 
template<typename T>
struct tensor<1, T> : public vector<T> {
    tensor(int n = 0, T val = T()) : vector<T>(n, val) {}
};

const int MAXN = 2e5 + 5;
const int MAXR = 500 * 505;
const int B = 500;

int N, R, Q, H[MAXN], r1[MAXN], r2[MAXN];
vector<int> adj[MAXN];
bool heavy[MAXR];
vector<int> inRegion[MAXR];

int sum[MAXN], target;
ll total_sum[MAXR];

void dfs(int u, vector<ll>& total_sum){
    total_sum[H[u]] += sum[u];
    sum[u] += (H[u] == target);
    for(int v : adj[u]){
        sum[v] = sum[u];
        dfs(v, total_sum);
    }
}

int timerDFS, tin[MAXN], tout[MAXN];
vector<int> pos[MAXR];
vector<ll> save[MAXR];

void init_dfs(int u){
    tin[u] = ++timerDFS;
    pos[H[u]].push_back(tin[u]);
    for(int v : adj[u]){
        init_dfs(v);
    }

    tout[u] = timerDFS;
}

int count(int i, int l, int r){
    return upper_bound(all(pos[i]), r) - lower_bound(all(pos[i]), l);
}

void testcase(){
    scanf("%d%d%d", &N, &R, &Q);
    for(int i = 1; i <= N; ++i){
        if(i > 1){
            int p;
            scanf("%d", &p);
            adj[p].push_back(i);
        }

        scanf("%d", &H[i]);
        inRegion[H[i]].push_back(i);
    }

    for(int i = 1; i <= R; ++i){
        if(sz(inRegion[i]) > B){
            heavy[i] = true;
            sum[1] = 0;
            save[i].resize(N + 1);
            target = i;
            dfs(1, save[i]);
        } else{
            heavy[i] = false;
        }
    }

    init_dfs(1);

    for(int i = 1; i <= Q; ++i){
        int r1, r2;
        scanf("%d%d", &r1, &r2);
        if(heavy[r1]){
            cout << save[r1][r2] << endl;
        } else{
            ll ans = 0;
            for(int u : inRegion[r1]){
                ans += count(r2, tin[u], tout[u]);
            }

            if(r1 == r2){ //2x times
                ans -= sz(inRegion[r1]);
            }

            cout << ans << endl;
        }
    }
}

int main(){
    int T = 1;
    // cin >> T;
    while(T--){
        testcase();
    }

    return 0;
}

Compilation message

regions.cpp: In function 'void testcase()':
regions.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     scanf("%d%d%d", &N, &R, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
regions.cpp:87:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |             scanf("%d", &p);
      |             ~~~~~^~~~~~~~~~
regions.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf("%d", &H[i]);
      |         ~~~~~^~~~~~~~~~~~~
regions.cpp:111:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         scanf("%d%d", &r1, &r2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 22872 KB Output is correct
2 Correct 9 ms 22872 KB Output is correct
3 Correct 13 ms 22872 KB Output is correct
4 Correct 10 ms 22872 KB Output is correct
5 Correct 11 ms 22872 KB Output is correct
6 Correct 18 ms 22872 KB Output is correct
7 Correct 24 ms 22872 KB Output is correct
8 Correct 24 ms 22872 KB Output is correct
9 Correct 32 ms 23384 KB Output is correct
10 Correct 57 ms 23384 KB Output is correct
11 Correct 96 ms 23640 KB Output is correct
12 Correct 112 ms 24152 KB Output is correct
13 Correct 145 ms 23900 KB Output is correct
14 Correct 205 ms 24408 KB Output is correct
15 Correct 201 ms 26456 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1580 ms 34940 KB Output is correct
2 Correct 1801 ms 34932 KB Output is correct
3 Correct 2343 ms 36800 KB Output is correct
4 Correct 207 ms 24420 KB Output is correct
5 Correct 262 ms 25688 KB Output is correct
6 Correct 1149 ms 25688 KB Output is correct
7 Correct 1427 ms 26964 KB Output is correct
8 Correct 1059 ms 30800 KB Output is correct
9 Correct 1949 ms 32040 KB Output is correct
10 Correct 3607 ms 35764 KB Output is correct
11 Correct 3749 ms 32080 KB Output is correct
12 Correct 1240 ms 37348 KB Output is correct
13 Correct 1622 ms 37552 KB Output is correct
14 Correct 1835 ms 68928 KB Output is correct
15 Correct 2588 ms 41972 KB Output is correct
16 Correct 2532 ms 47288 KB Output is correct
17 Correct 2260 ms 78972 KB Output is correct