oj.uz

Submission #146024

# Submission time Handle Problem Language Result Execution time Memory
146024 2019-08-21T15:30:58 Z popovicirobert Regions (IOI09_regions) C++14
0 / 100
 167 ms 29080 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long


#if 0
const int MOD = ;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}

inline int inv(int x) {
    return lgput(x, MOD - 2);
}
#endif

#if 0
int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}
#endif

using namespace std;

const int MAXN = (int) 2e5;
const int MAXR = 25000;
const int B = 500;

vector <int> g[MAXN + 1];
int id[MAXN + 1], fr[MAXR + 1];

vector <int> pos[MAXR + 1], nodes[MAXR + 1];
int idl[MAXN + 1], idr[MAXN + 1], sz;

void dfs(int nod) {
    idl[nod] = ++sz;
    nodes[id[nod]].push_back(nod);
    pos[id[nod]].push_back(sz);
    for(auto it : g[nod]) {
        dfs(it);
    }
    idr[nod] = sz;
}

ll cnt[B][MAXR + 1];
int where[MAXR + 1], vals[MAXN + 1];

void dfs1(int nod, int num) {
    for(int i = 0; i < num; i++) {
        cnt[i][id[nod]] += fr[vals[i]];
    }
    fr[id[nod]]++;
    for(auto it : g[nod]) {
        dfs1(it, num);
    }
    fr[id[nod]]--;
}

int main() {
#if 0
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, n, r, q;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> r >> q;
    cin >> id[1];
    for(i = 2; i <= n; i++) {
        int par;
        cin >> par >> id[i];
        g[par].push_back(i);
    }
    for(i = 1; i <= n; i++) {
        fr[id[i]]++;
    }
    dfs(1);

    int num = 0;
    for(i = 1; i <= r; i++) {
        if(fr[i] >= B) {
            vals[num] = i;
            where[i] = num;
            num++;
        }
    }

    fill(fr, fr + MAXR + 1, 0);
    dfs1(1, num);

    while(q--) {
        int r1, r2;
        cin >> r1 >> r2;
        ll ans = 0;
        if(fr[r1] < B) {
            for(auto nod : nodes[r1]) {
                ans += upper_bound(pos[r2].begin(), pos[r2].end(), idr[nod]) - lower_bound(pos[r2].begin(), pos[r2].end(), idl[nod] + 1);
            }
        }
        else {
            ans = cnt[where[r1]][r2];
        }
        cout << ans << "\n";
    }

    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7 ms 6312 KB Time limit exceeded (wall clock)
2 Execution timed out 7 ms 6392 KB Time limit exceeded (wall clock)
3 Execution timed out 7 ms 6268 KB Time limit exceeded (wall clock)
4 Execution timed out 7 ms 6264 KB Time limit exceeded (wall clock)
5 Execution timed out 7 ms 6396 KB Time limit exceeded (wall clock)
6 Execution timed out 7 ms 6392 KB Time limit exceeded (wall clock)
7 Execution timed out 7 ms 6392 KB Time limit exceeded (wall clock)
8 Execution timed out 7 ms 6392 KB Time limit exceeded (wall clock)
9 Execution timed out 9 ms 6776 KB Time limit exceeded (wall clock)
10 Execution timed out 12 ms 6776 KB Time limit exceeded (wall clock)
11 Execution timed out 13 ms 7032 KB Time limit exceeded (wall clock)
12 Execution timed out 15 ms 7592 KB Time limit exceeded (wall clock)
13 Execution timed out 17 ms 7236 KB Time limit exceeded (wall clock)
14 Execution timed out 20 ms 7928 KB Time limit exceeded (wall clock)
15 Execution timed out 22 ms 10468 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 39 ms 11000 KB Time limit exceeded (wall clock)
2 Execution timed out 41 ms 9900 KB Time limit exceeded (wall clock)
3 Execution timed out 41 ms 12792 KB Time limit exceeded (wall clock)
4 Execution timed out 22 ms 7928 KB Time limit exceeded (wall clock)
5 Execution timed out 23 ms 9512 KB Time limit exceeded (wall clock)
6 Execution timed out 42 ms 10428 KB Time limit exceeded (wall clock)
7 Execution timed out 46 ms 10232 KB Time limit exceeded (wall clock)
8 Execution timed out 54 ms 15480 KB Time limit exceeded (wall clock)
9 Execution timed out 99 ms 15652 KB Time limit exceeded (wall clock)
10 Execution timed out 98 ms 20568 KB Time limit exceeded (wall clock)
11 Execution timed out 124 ms 15532 KB Time limit exceeded (wall clock)
12 Execution timed out 151 ms 17152 KB Time limit exceeded (wall clock)
13 Execution timed out 127 ms 17360 KB Time limit exceeded (wall clock)
14 Execution timed out 167 ms 20524 KB Time limit exceeded (wall clock)
15 Execution timed out 129 ms 21752 KB Time limit exceeded (wall clock)
16 Execution timed out 106 ms 27128 KB Time limit exceeded (wall clock)
17 Execution timed out 136 ms 29080 KB Time limit exceeded (wall clock)