oj.uz

Submission #228817

# Submission time Handle Problem Language Result Execution time Memory
228817 2020-05-02T17:06:04 Z osaaateiasavtnl Regions (IOI09_regions) C++14
100 / 100
 6580 ms 97708 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#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;
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() > 500) {
            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 39 ms 59128 KB Output is correct
2 Correct 38 ms 59008 KB Output is correct
3 Correct 39 ms 59008 KB Output is correct
4 Correct 45 ms 59112 KB Output is correct
5 Correct 47 ms 59136 KB Output is correct
6 Correct 52 ms 59344 KB Output is correct
7 Correct 70 ms 59384 KB Output is correct
8 Correct 76 ms 59568 KB Output is correct
9 Correct 93 ms 60024 KB Output is correct
10 Correct 136 ms 60536 KB Output is correct
11 Correct 191 ms 61304 KB Output is correct
12 Correct 219 ms 62048 KB Output is correct
13 Correct 269 ms 62328 KB Output is correct
14 Correct 389 ms 63224 KB Output is correct
15 Correct 326 ms 65884 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1551 ms 69088 KB Output is correct
2 Correct 1851 ms 68344 KB Output is correct
3 Correct 2631 ms 73212 KB Output is correct
4 Correct 385 ms 64224 KB Output is correct
5 Correct 471 ms 66152 KB Output is correct
6 Correct 725 ms 66704 KB Output is correct
7 Correct 961 ms 68172 KB Output is correct
8 Correct 1510 ms 76260 KB Output is correct
9 Correct 2964 ms 85336 KB Output is correct
10 Correct 5221 ms 91144 KB Output is correct
11 Correct 6580 ms 91124 KB Output is correct
12 Correct 2125 ms 84452 KB Output is correct
13 Correct 2856 ms 86556 KB Output is correct
14 Correct 3300 ms 88952 KB Output is correct
15 Correct 4235 ms 94512 KB Output is correct
16 Correct 3823 ms 97708 KB Output is correct
17 Correct 4230 ms 97524 KB Output is correct