oj.uz

Submission #146026

# Submission time Handle Problem Language Result Execution time Memory
146026 2019-08-21T15:41:14 Z popovicirobert Regions (IOI09_regions) C++14
0 / 100
 284 ms 131076 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;

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];
vector < vector <ll> > cnt;

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, B = sqrt(n / (q * log2(n)));
    for(i = 1; i <= r; i++) {
        if(fr[i] >= B) {
            vals[num] = i;
            where[i] = num++;
        }
    }

    cnt.resize(num, vector <ll>(n + 1));
    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 6392 KB Time limit exceeded (wall clock)
2 Execution timed out 7 ms 6264 KB Time limit exceeded (wall clock)
3 Execution timed out 7 ms 6264 KB Time limit exceeded (wall clock)
4 Execution timed out 7 ms 6392 KB Time limit exceeded (wall clock)
5 Execution timed out 7 ms 6520 KB Time limit exceeded (wall clock)
6 Execution timed out 9 ms 8056 KB Time limit exceeded (wall clock)
7 Execution timed out 10 ms 8184 KB Time limit exceeded (wall clock)
8 Execution timed out 12 ms 9592 KB Time limit exceeded (wall clock)
9 Execution timed out 25 ms 18552 KB Time limit exceeded (wall clock)
10 Execution timed out 57 ms 39800 KB Time limit exceeded (wall clock)
11 Execution timed out 57 ms 38980 KB Time limit exceeded (wall clock)
12 Execution timed out 173 ms 79864 KB Time limit exceeded (wall clock)
13 Execution timed out 148 ms 71416 KB Time limit exceeded (wall clock)
14 Execution timed out 116 ms 55288 KB Time limit exceeded (wall clock)
15 Execution timed out 181 ms 86648 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 284 ms 129256 KB Time limit exceeded (wall clock)
2 Runtime error 143 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 140 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 125 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 124 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 136 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 145 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 149 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 186 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 186 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 205 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 222 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 201 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 234 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 205 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 189 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 188 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)