oj.uz

Submission #146039

# Submission time Handle Problem Language Result Execution time Memory
146039 2019-08-21T16:32:08 Z popovicirobert Regions (IOI09_regions) C++14
75 / 100
 8000 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;
const int B = 500;

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

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

void dfs(int nod) {
    idl[nod] = ++sz;

    nodes1[id[nod]].push_back(nod);
    pos[id[nod]].push_back(sz);

    for(auto it : g[nod]) {
        dfs(it);
    }
    nodes2[id[nod]].push_back(nod);
    idr[nod] = sz;
}

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

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

ll cnt2[MAXR + 1][MAXN / B];
int w[MAXN + 1];

void dfs2(int nod, int cur) {
    w[nod] = 0;
    for(auto it : g[nod]) {
        dfs2(it, cur);
        w[nod] += w[it];
    }
    cnt2[id[nod]][cur] += w[nod];
    w[nod] += (where[id[nod]] == cur);
}

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);

    for(i = 0; i < num; i++) {
        dfs2(1, i);
    }

    while(q--) {
        int r1, r2;
        cin >> r1 >> r2;
        ll ans = 0;
        if(fr[r1] < B && fr[r2] < B) {
            int sz = pos[r2].size();
            int p = 0;
            for(auto nod : nodes1[r1]) {
                while(p < sz && pos[r2][p] <= idl[nod]) p++;
                ans -= p;
            }
            p = 0;
            for(auto nod : nodes2[r1]) {
                while(p < sz && pos[r2][p] <= idr[nod]) p++;
                ans += p;
            }
        }
        else {
            ans = (fr[r1] >= B ? cnt1[r2][where[r1]] : cnt2[r1][where[r2]]);
        }
        cout << ans << "\n";
        cout.flush();
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6904 KB Output is correct
2 Correct 10 ms 6904 KB Output is correct
3 Correct 10 ms 6904 KB Output is correct
4 Correct 12 ms 6904 KB Output is correct
5 Correct 15 ms 6904 KB Output is correct
6 Correct 22 ms 7032 KB Output is correct
7 Correct 41 ms 7036 KB Output is correct
8 Correct 54 ms 7032 KB Output is correct
9 Correct 64 ms 7416 KB Output is correct
10 Correct 61 ms 7416 KB Output is correct
11 Correct 132 ms 7800 KB Output is correct
12 Correct 156 ms 8444 KB Output is correct
13 Correct 144 ms 8104 KB Output is correct
14 Correct 253 ms 8696 KB Output is correct
15 Correct 275 ms 11384 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4106 ms 13488 KB Output is correct
2 Execution timed out 8045 ms 12604 KB Time limit exceeded
3 Correct 6286 ms 15836 KB Output is correct
4 Correct 313 ms 8872 KB Output is correct
5 Correct 439 ms 10360 KB Output is correct
6 Correct 1006 ms 50216 KB Output is correct
7 Correct 1360 ms 11512 KB Output is correct
8 Correct 1347 ms 79568 KB Output is correct
9 Correct 2013 ms 17636 KB Output is correct
10 Correct 2953 ms 22648 KB Output is correct
11 Correct 3784 ms 17856 KB Output is correct
12 Correct 3565 ms 110536 KB Output is correct
13 Correct 4027 ms 110592 KB Output is correct
14 Runtime error 317 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 238 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 209 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 222 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)