oj.uz

Submission #731701

# Submission time Handle Problem Language Result Execution time Memory
731701 2023-04-27T20:10:13 Z Desh03 Regions (IOI09_regions) C++17
30 / 100
 8000 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> r, g;
vector<int> euler, in, out, fr, c;
vector<vector<pair<int, int>>> q;
int t;
const int block = 447;

void dfs(int u) {
    in[u] = t++;
    euler.push_back(u);
    for (int v : g[u])
        dfs(v);
    out[u] = t - 1;
}

void add(int x) {
    fr[c[euler[x]]]++;
}

void remove(int x) {
    fr[c[euler[x]]]--;
}

int main() {
    int n, rr, qq;
    cin >> n >> rr >> qq;
    g.resize(n), r.resize(rr), in.resize(n), out.resize(n), fr.resize(rr), c.resize(n), q.resize(qq);

    int x, h;
    cin >> h;
    h--;
    r[h].push_back(0);
    c[0] = h;
    int mx = 0;
    for (int i = 1; i < n; i++) {
        cin >> x >> h;
        x--, h--;
        r[h].push_back(i);
        g[x].push_back(i);
        c[i] = h;
        mx = max(mx, (int) r[h].size());
    }
    dfs(0);
    if (rr <= 1500) {
        vector<vector<int>> ans(rr, vector<int> (rr));
        for (int i = 0; i < rr; i++) {
            sort(r[i].begin(), r[i].end(), [](const int &a, const int &b) {
                 int a1 = in[a] / block, b1 = in[b] / block;
                 return a1 == b1 ? out[a] < out[b] : a1 < b1;
            });
        }
        for (int i = 0; i < rr; i++) {
            int lb, rb;
            if (r[i].size()) lb = in[r[i][0]] + 1, rb = lb - 1;
            for (int u : r[i]) {
                int l_ = in[u] + 1, r_ = out[u];
                while (lb > l_) add(--lb);
                while (rb < r_) add(++rb);
                while (lb < l_) remove(lb++);
                while (rb > r_) remove(rb--);
                for (int j = 0; j < rr; j++) ans[i][j] += fr[j];
            }
            if (r[i].size()) for (int j = 0; j < rr; j++) fr[j] = 0;
        }
        while (qq--) {
            int a, b;
            cin >> a >> b;
            cout << ans[--a][--b] << endl;
        }
    } else {
        map<int, map<int, int>> mp;
        map<pair<int, int>, int> mp2;
        for (int i = 0; i < rr; i++) {
            sort(r[i].begin(), r[i].end(), [](const int &a, const int &b) {
                 int a1 = in[a] / block, b1 = in[b] / block;
                 return a1 == b1 ? out[a] < out[b] : a1 < b1;
            });
        }
        while (qq--) {
            int a, b, ans = 0, cnt = 0;
            cin >> a >> b;
            a--, b--;
            if (mp2.find({a, b}) != mp2.end()) {
                cout << mp2[{a, b}] << '\n';
                continue;
            }
            int lb, rb;
            if (r[a].size()) lb = in[r[a][0]] + 1, rb = lb - 1;
            for (int u : r[a]) {
                if (mp[u].find(b) != mp[u].end()) cnt += mp[u][b];
                else {
                    int l_ = in[u] + 1, r_ = out[u];
                    while (lb > l_) add(--lb);
                    while (rb < r_) add(++rb);
                    while (lb < l_) remove(lb++);
                    while (rb > r_) remove(rb--);
                    mp[u][b] = cnt;
                    ans += cnt;
                }
            }
            cout << ans << endl;
            mp2[{a, b}] = ans;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 2 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 22 ms 592 KB Output is correct
7 Correct 32 ms 464 KB Output is correct
8 Correct 29 ms 592 KB Output is correct
9 Correct 62 ms 1360 KB Output is correct
10 Correct 124 ms 1956 KB Output is correct
11 Correct 156 ms 2000 KB Output is correct
12 Correct 318 ms 3152 KB Output is correct
13 Correct 231 ms 2604 KB Output is correct
14 Correct 260 ms 3024 KB Output is correct
15 Correct 280 ms 6084 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1767 ms 8808 KB Output is correct
2 Correct 1249 ms 7976 KB Output is correct
3 Correct 2048 ms 12280 KB Output is correct
4 Execution timed out 8005 ms 53828 KB Time limit exceeded
5 Execution timed out 8039 ms 45368 KB Time limit exceeded
6 Execution timed out 8096 ms 36696 KB Time limit exceeded
7 Execution timed out 8074 ms 35932 KB Time limit exceeded
8 Execution timed out 8028 ms 46928 KB Time limit exceeded
9 Execution timed out 8031 ms 35420 KB Time limit exceeded
10 Execution timed out 8051 ms 52592 KB Time limit exceeded
11 Execution timed out 8012 ms 40912 KB Time limit exceeded
12 Execution timed out 8026 ms 81776 KB Time limit exceeded
13 Runtime error 7786 ms 131072 KB Execution killed with signal 9
14 Execution timed out 8047 ms 80628 KB Time limit exceeded
15 Runtime error 7278 ms 131072 KB Execution killed with signal 9
16 Runtime error 2299 ms 131072 KB Execution killed with signal 9
17 Execution timed out 8077 ms 124368 KB Time limit exceeded