oj.uz

Submission #731703

# Submission time Handle Problem Language Result Execution time Memory
731703 2023-04-27T20:12:10 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 <= 1000 || mx > 500) {
        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 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 4 ms 208 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 9 ms 336 KB Output is correct
6 Correct 22 ms 592 KB Output is correct
7 Correct 28 ms 464 KB Output is correct
8 Correct 41 ms 720 KB Output is correct
9 Correct 65 ms 1360 KB Output is correct
10 Correct 113 ms 1872 KB Output is correct
11 Correct 190 ms 2000 KB Output is correct
12 Correct 293 ms 3152 KB Output is correct
13 Correct 259 ms 2600 KB Output is correct
14 Correct 251 ms 3020 KB Output is correct
15 Correct 312 ms 5944 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1650 ms 8780 KB Output is correct
2 Correct 1231 ms 8004 KB Output is correct
3 Correct 1762 ms 12404 KB Output is correct
4 Execution timed out 8013 ms 51480 KB Time limit exceeded
5 Execution timed out 8007 ms 46256 KB Time limit exceeded
6 Execution timed out 8023 ms 34904 KB Time limit exceeded
7 Execution timed out 8089 ms 35648 KB Time limit exceeded
8 Execution timed out 8039 ms 46472 KB Time limit exceeded
9 Execution timed out 8022 ms 34240 KB Time limit exceeded
10 Execution timed out 8042 ms 54404 KB Time limit exceeded
11 Execution timed out 8103 ms 41016 KB Time limit exceeded
12 Runtime error 180 ms 131072 KB Execution killed with signal 9
13 Runtime error 173 ms 131072 KB Execution killed with signal 9
14 Runtime error 187 ms 131072 KB Execution killed with signal 9
15 Runtime error 183 ms 131072 KB Execution killed with signal 9
16 Runtime error 168 ms 131072 KB Execution killed with signal 9
17 Runtime error 176 ms 131072 KB Execution killed with signal 9