oj.uz

Submission #146028

# Submission time Handle Problem Language Result Execution time Memory
146028 2019-08-21T15:52:10 Z popovicirobert Regions (IOI09_regions) C++14
65 / 100
 8000 ms 104876 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;
}

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

void dfs1(int nod, int num) {
    for(int i = 0; i < num; i++) {
        cnt[id[nod]][i] += 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++;
        }
    }

    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[r2][where[r1]];
        }
        cout << ans << "\n";
        cout.flush();
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6392 KB Output is correct
2 Correct 7 ms 6264 KB Output is correct
3 Correct 9 ms 6392 KB Output is correct
4 Correct 12 ms 6392 KB Output is correct
5 Correct 16 ms 6264 KB Output is correct
6 Correct 16 ms 6392 KB Output is correct
7 Correct 38 ms 6408 KB Output is correct
8 Correct 41 ms 6520 KB Output is correct
9 Correct 49 ms 6776 KB Output is correct
10 Correct 97 ms 6884 KB Output is correct
11 Correct 104 ms 7156 KB Output is correct
12 Correct 172 ms 7544 KB Output is correct
13 Correct 182 ms 7352 KB Output is correct
14 Correct 293 ms 7920 KB Output is correct
15 Correct 388 ms 10488 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8050 ms 11640 KB Time limit exceeded
2 Execution timed out 8076 ms 10488 KB Time limit exceeded
3 Execution timed out 8003 ms 13508 KB Time limit exceeded
4 Correct 302 ms 7908 KB Output is correct
5 Correct 423 ms 9592 KB Output is correct
6 Correct 1698 ms 29304 KB Output is correct
7 Correct 1918 ms 10232 KB Output is correct
8 Correct 1370 ms 46584 KB Output is correct
9 Correct 2923 ms 15780 KB Output is correct
10 Correct 5195 ms 20736 KB Output is correct
11 Correct 5858 ms 15580 KB Output is correct
12 Correct 5652 ms 62580 KB Output is correct
13 Correct 6659 ms 62768 KB Output is correct
14 Execution timed out 8060 ms 72872 KB Time limit exceeded
15 Execution timed out 8074 ms 99576 KB Time limit exceeded
16 Execution timed out 8048 ms 104876 KB Time limit exceeded
17 Execution timed out 8023 ms 82128 KB Time limit exceeded