oj.uz

Submission #228818

# Submission time Handle Problem Language Result Execution time Memory
228818 2020-05-02T17:07:15 Z osaaateiasavtnl Regions (IOI09_regions) C++14
100 / 100
 5995 ms 92204 KB 
#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 5e5 + 7, K = 400;

int n, R, q;
int color[N], par[N];
vector <int> tree[N], pos[N], who[N];
int l[N], r[N], ptr = 0;
void dfs(int u) {
    l[u] = ++ptr;
    pos[color[u]].app(l[u]);
    for (int v : tree[u]) {
        dfs(v);
    }   
    r[u] = ptr;
}   

vector <int> cl[N], cr[N];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #endif
    cin >> n >> R >> q;
    cin >> color[1];
    for (int i = 2; i <= n; ++i) {
        cin >> par[i] >> color[i];
        tree[par[i]].app(i);
    }   
    for (int i = 1; i <= n; ++i)
        who[color[i]].app(i);
    dfs(1);
    for (int i = 1; i <= n; ++i) {
        cl[color[i]].app(l[i]);
        cr[color[i]].app(r[i]);
    }   
    for (int i = 1; i <= R; ++i) {
        sort(all(cl[i]));
        sort(all(cr[i]));
    }   
    map <ii, int> mem;
    while (q--) {
        int c1, c2;
        cin >> c1 >> c2;

        if (mem.find(mp(c1, c2)) != mem.end()) {
            cout << mem[mp(c1, c2)] << endl;
            continue;
        }

        int ans = 0;
        if (who[c2].size() > K) {
            vector <int> &a = pos[c2];
            for (int u : who[c1]) {
                ans += upper_bound(all(a), r[u]) - upper_bound(all(a), l[u]);
            }   
        }
        else {
            for (int u : who[c2]) {
                ans += (lower_bound(all(cl[c1]), l[u]) - cl[c1].begin()) - (lower_bound(all(cr[c1]), l[u]) - cr[c1].begin());
            }   
        }

        mem[mp(c1, c2)] = ans;
        cout << ans << endl;
        fflush(stdout);
    }   
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 59000 KB Output is correct
2 Correct 45 ms 59008 KB Output is correct
3 Correct 45 ms 59000 KB Output is correct
4 Correct 40 ms 59136 KB Output is correct
5 Correct 48 ms 59136 KB Output is correct
6 Correct 56 ms 59312 KB Output is correct
7 Correct 69 ms 59384 KB Output is correct
8 Correct 74 ms 59384 KB Output is correct
9 Correct 92 ms 59896 KB Output is correct
10 Correct 133 ms 60152 KB Output is correct
11 Correct 176 ms 60664 KB Output is correct
12 Correct 210 ms 61304 KB Output is correct
13 Correct 253 ms 61432 KB Output is correct
14 Correct 371 ms 61944 KB Output is correct
15 Correct 319 ms 64120 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1443 ms 66296 KB Output is correct
2 Correct 1738 ms 65348 KB Output is correct
3 Correct 2423 ms 70208 KB Output is correct
4 Correct 366 ms 62976 KB Output is correct
5 Correct 454 ms 64800 KB Output is correct
6 Correct 670 ms 65016 KB Output is correct
7 Correct 953 ms 65580 KB Output is correct
8 Correct 1276 ms 72916 KB Output is correct
9 Correct 2933 ms 79460 KB Output is correct
10 Correct 4827 ms 85776 KB Output is correct
11 Correct 5995 ms 84280 KB Output is correct
12 Correct 2023 ms 77884 KB Output is correct
13 Correct 2718 ms 79920 KB Output is correct
14 Correct 3436 ms 81688 KB Output is correct
15 Correct 4256 ms 88268 KB Output is correct
16 Correct 3505 ms 92204 KB Output is correct
17 Correct 3830 ms 90636 KB Output is correct