oj.uz

Submission #574167

# Submission time Handle Problem Language Result Execution time Memory
574167 2022-06-08T05:32:02 Z RandomLB Regions (IOI09_regions) C++17
100 / 100
 4789 ms 35552 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
template<class T> using indexed_set = tree<T, null_type, less_equal<T>,
        rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order //(k-indexed val with 0-indexing)
#define ook order_of_key //(num of vals in set that are strictly less)
#define ms(x, a) memset(x, a, sizeof(x))
#define siz(x) (int)x.size()
#define len(x) (int)x.length()
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define F first
#define S second
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vals, Args&&... values){
    cout << vals << " = ";
    string delim = "";
    (...,(cout << delim << values, delim = ", "));
    cout << endl;
}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;
//===========================================
const int MAX = 2e5+5;
const int BLOCK = 500;
vector<int> adj[MAX], comp[MAX], occ[MAX];
int cmp[MAX], in[MAX], sub[MAX], res[400][25005], pp[MAX], curr;

int dfs(int v){
    in[v] = ++curr;
    occ[cmp[v]].pb(in[v]);
    for (int u: adj[v]) sub[v] += dfs(u);
    return (sub[v] += 1);
}

void dfs2(int v, int tar, int curr){
    if (cmp[v] == tar) curr++;
    res[pp[tar]][cmp[v]] += curr;
    for (int u: adj[v]) dfs2(u, tar, curr);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    //freopen("test.txt", "r", stdin);
    int n, r, q; cin >> n >> r >> q;
    for (int i = 1; i <= n; i++){
        if (i > 1){
            int a; cin >> a;
            adj[a].pb(i);
        }
        cin >> cmp[i];
        comp[cmp[i]].pb(i);
    }
    dfs(1);
    curr = 0;
    for (int i = 1; i <= r; i++){
        if (siz(comp[i]) < BLOCK) continue;
        pp[i] = ++curr;
        dfs2(1, i, 0);
    }
    while (q--){
        int a, b; cin >> a >> b;
        if (pp[a]) cout << res[pp[a]][b] << endl;
        else {
            int tot = 0;
            for (int v: comp[a]){
                tot += lower_bound(all(occ[b]), in[v]+sub[v])-lower_bound(all(occ[b]), in[v]);
            }
            cout << tot << endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14416 KB Output is correct
2 Correct 7 ms 14416 KB Output is correct
3 Correct 10 ms 14416 KB Output is correct
4 Correct 13 ms 14416 KB Output is correct
5 Correct 14 ms 14416 KB Output is correct
6 Correct 22 ms 14460 KB Output is correct
7 Correct 35 ms 14416 KB Output is correct
8 Correct 37 ms 14544 KB Output is correct
9 Correct 43 ms 14848 KB Output is correct
10 Correct 89 ms 14956 KB Output is correct
11 Correct 124 ms 15184 KB Output is correct
12 Correct 153 ms 15736 KB Output is correct
13 Correct 160 ms 15440 KB Output is correct
14 Correct 304 ms 15956 KB Output is correct
15 Correct 248 ms 18456 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1888 ms 19112 KB Output is correct
2 Correct 2031 ms 17964 KB Output is correct
3 Correct 2539 ms 20888 KB Output is correct
4 Correct 273 ms 16020 KB Output is correct
5 Correct 397 ms 17616 KB Output is correct
6 Correct 1224 ms 17888 KB Output is correct
7 Correct 1806 ms 18328 KB Output is correct
8 Correct 1485 ms 23484 KB Output is correct
9 Correct 2375 ms 23776 KB Output is correct
10 Correct 3971 ms 28744 KB Output is correct
11 Correct 4789 ms 23712 KB Output is correct
12 Correct 1302 ms 25232 KB Output is correct
13 Correct 2017 ms 25432 KB Output is correct
14 Correct 2457 ms 27012 KB Output is correct
15 Correct 3232 ms 29728 KB Output is correct
16 Correct 3316 ms 34992 KB Output is correct
17 Correct 2956 ms 35552 KB Output is correct