oj.uz

Submission #738480

# Submission time Handle Problem Language Result Execution time Memory
738480 2023-05-08T20:28:49 Z lorenzoferrari Regions (IOI09_regions) C++17
40 / 100
 8000 ms 34024 KB 
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
using LL = long long;

static constexpr int SQ = 500;

struct Segtree {
    int n;
    vector<int> t;
    Segtree(int n) : n(n), t(2*n) {}
    void update(int p, int v) {
        for (t[p += n] += v; p > 1; p >>= 1) {
            t[p >> 1] = t[p] + t[p ^ 1];
        }
    }
    int query(int l, int r) {
        int ans = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ans += t[l++];
            if (r & 1) ans += t[--r];
        }
        return ans;
    }
};

int main() {
    int n; cin >> n;
    int r; cin >> r;
    int q; cin >> q;
    vector<int> h(n), p(n), f(r);
    vector<vector<int>> adj(n);
    cin >> h[0]; ++f[--h[0]];
    for (int i = 1; i < n; ++i) {
        cin >> p[i] >> h[i];
        --p[i], --h[i];
        adj[p[i]].push_back(i);
        ++f[h[i]];
    }
    vector<int> ff;
    vector<int> fi(r, -1);
    for (int i = 0; i < r; ++i) {
        if (f[i] >= SQ) {
            fi[i] = ff.size();
            ff.push_back(i);
        }
    }
    int nn = ff.size();

    vector<int> in(n), out(n), ord;
    { // linearize the tree
        int t = 0;
        auto dfs = [&](auto&& self, int v) -> void {
            in[v] = t++;
            ord.push_back(v);
            for (int u : adj[v]) {
                self(self, u);
            }
            out[v] = t;
        };
        dfs(dfs, 0);
    }

    vector<vector<int>> vs(r);
    {
        for (int v : ord) {
            int c = h[v];
            vs[h[v]].push_back(v);
        }
    }

    vector<vector<LL>> sub(r, vector<LL>(nn));
    vector<vector<LL>> anc(r, vector<LL>(nn));
    {
        auto dfs = [&](auto&& self, int v, int i, int acc = 0) -> int {
            int cnt = 0;
            for (int u : adj[v]) {
                cnt += self(self, u, i, acc + (h[v] == ff[i]));
            }
            sub[h[v]][i] += cnt;
            anc[h[v]][i] += acc;
            return cnt + (h[v] == ff[i]);
        };
        for (int i = 0; i < nn; ++i) {
            dfs(dfs, 0, i);
        }
    }

    Segtree st(n);
    for (int r1, r2; q--;) {
        cin >> r1 >> r2;
        --r1, --r2;
        if (f[r2] >= SQ) {
            cout << sub[r1][fi[r2]] << endl;
        } else if (f[r1] >= SQ) {
            cout << anc[r2][fi[r2]] << endl;
        } else {
            LL ans = 0;
            for (int v : vs[r2]) {
                st.update(in[v], 1);
            }
            for (int u : vs[r1]) {
                ans += st.query(in[u]+1, out[u]);
            }
            for (int v : vs[r2]) {
                st.update(in[v], -1);
            }
            cout << ans << endl;
        }
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:68:17: warning: unused variable 'c' [-Wunused-variable]
   68 |             int c = h[v];
      |                 ^

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 2 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 9 ms 336 KB Output is correct
7 Correct 30 ms 336 KB Output is correct
8 Correct 47 ms 464 KB Output is correct
9 Correct 66 ms 848 KB Output is correct
10 Correct 89 ms 1232 KB Output is correct
11 Correct 162 ms 1652 KB Output is correct
12 Correct 208 ms 2236 KB Output is correct
13 Correct 223 ms 2128 KB Output is correct
14 Correct 305 ms 2892 KB Output is correct
15 Correct 681 ms 5024 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1843 ms 7428 KB Output isn't correct
2 Incorrect 1648 ms 6528 KB Output isn't correct
3 Incorrect 3994 ms 9632 KB Output isn't correct
4 Correct 434 ms 3192 KB Output is correct
5 Correct 359 ms 4724 KB Output is correct
6 Incorrect 1407 ms 7660 KB Output isn't correct
7 Correct 2771 ms 7232 KB Output is correct
8 Incorrect 3442 ms 13448 KB Output isn't correct
9 Correct 4837 ms 15232 KB Output is correct
10 Execution timed out 8032 ms 20116 KB Time limit exceeded
11 Correct 6355 ms 17792 KB Output is correct
12 Incorrect 1840 ms 19516 KB Output isn't correct
13 Incorrect 3149 ms 19532 KB Output isn't correct
14 Incorrect 3383 ms 26440 KB Output isn't correct
15 Incorrect 6034 ms 24672 KB Output isn't correct
16 Incorrect 6530 ms 29516 KB Output isn't correct
17 Incorrect 5905 ms 34024 KB Output isn't correct