oj.uz

Submission #146042

# Submission time Handle Problem Language Result Execution time Memory
146042 2019-08-21T16:39:00 Z popovicirobert Regions (IOI09_regions) C++14
100 / 100
 6769 ms 30584 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 = 700;

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

vector <int> in[MAXR + 1], out[MAXR + 1];
int sz;

void dfs(int nod) {
    in[id[nod]].push_back(++sz);
    for(auto it : g[nod]) {
        dfs(it);
    }
    out[id[nod]].push_back(sz);
}

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

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

ll cnt2[MAXN / B][MAXR + 1];
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[cur][id[nod]] += 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 = in[r2].size();
            int p = 0;
            for(auto it : in[r1]) {
                while(p < sz && in[r2][p] <= it) p++;
                ans -= p;
            }
            p = 0;
            for(auto it : out[r1]) {
                while(p < sz && in[r2][p] <= it) p++;
                ans += p;
            }
        }
        else {
            ans = (fr[r1] >= B ? cnt1[where[r1]][r2] : cnt2[where[r2]][r1]);
        }
        cout << ans << "\n";
        cout.flush();
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6264 KB Output is correct
2 Correct 7 ms 6268 KB Output is correct
3 Correct 9 ms 6264 KB Output is correct
4 Correct 13 ms 6264 KB Output is correct
5 Correct 15 ms 6264 KB Output is correct
6 Correct 24 ms 6264 KB Output is correct
7 Correct 22 ms 6264 KB Output is correct
8 Correct 39 ms 6392 KB Output is correct
9 Correct 49 ms 6776 KB Output is correct
10 Correct 91 ms 6804 KB Output is correct
11 Correct 129 ms 6904 KB Output is correct
12 Correct 134 ms 7484 KB Output is correct
13 Correct 176 ms 7144 KB Output is correct
14 Correct 225 ms 7708 KB Output is correct
15 Correct 196 ms 10128 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3335 ms 10744 KB Output is correct
2 Correct 6769 ms 9720 KB Output is correct
3 Correct 5028 ms 12560 KB Output is correct
4 Correct 300 ms 7772 KB Output is correct
5 Correct 361 ms 9268 KB Output is correct
6 Correct 909 ms 8824 KB Output is correct
7 Correct 1215 ms 9720 KB Output is correct
8 Correct 1104 ms 14480 KB Output is correct
9 Correct 1849 ms 14628 KB Output is correct
10 Correct 2600 ms 19320 KB Output is correct
11 Correct 3188 ms 14144 KB Output is correct
12 Correct 2458 ms 16824 KB Output is correct
13 Correct 2946 ms 16888 KB Output is correct
14 Correct 3833 ms 21888 KB Output is correct
15 Correct 4364 ms 21652 KB Output is correct
16 Correct 4977 ms 26704 KB Output is correct
17 Correct 5217 ms 30584 KB Output is correct