oj.uz

Submission #146027

# Submission time Handle Problem Language Result Execution time Memory
146027 2019-08-21T15:43:58 Z popovicirobert Regions (IOI09_regions) C++14
0 / 100
 244 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>(r + 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 8 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 8 ms 6392 KB Time limit exceeded (wall clock)
6 Execution timed out 8 ms 6904 KB Time limit exceeded (wall clock)
7 Execution timed out 8 ms 6520 KB Time limit exceeded (wall clock)
8 Execution timed out 9 ms 6776 KB Time limit exceeded (wall clock)
9 Execution timed out 15 ms 7544 KB Time limit exceeded (wall clock)
10 Execution timed out 30 ms 8336 KB Time limit exceeded (wall clock)
11 Execution timed out 30 ms 7808 KB Time limit exceeded (wall clock)
12 Execution timed out 64 ms 9208 KB Time limit exceeded (wall clock)
13 Execution timed out 53 ms 8312 KB Time limit exceeded (wall clock)
14 Execution timed out 45 ms 8184 KB Time limit exceeded (wall clock)
15 Execution timed out 62 ms 10872 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 102 ms 11256 KB Time limit exceeded (wall clock)
2 Execution timed out 110 ms 10104 KB Time limit exceeded (wall clock)
3 Execution timed out 143 ms 13176 KB Time limit exceeded (wall clock)
4 Runtime error 129 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 126 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 137 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 147 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 146 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 191 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 206 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 226 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 207 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 244 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 206 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 191 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 190 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)