oj.uz

Submission #738471

# Submission time Handle Problem Language Result Execution time Memory
738471 2023-05-08T20:06:18 Z lorenzoferrari Regions (IOI09_regions) C++17
0 / 100
 2284 ms 26248 KB 
#include "bits/stdc++.h"
using namespace std;
using LL = long long;

static constexpr int SQ = 500;

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>> heads(r), all(r);
    {
        for (int v : ord) {
            int c = h[v];
            if (heads[c].empty() || out[heads[c].back()] < out[v]) {
                heads[c].push_back(v);
            }
            all[c].push_back(v);
        }
    }


    vector<vector<int>> ans(r, vector<int>(nn));
    {
        vector<int> cnt(n);
        auto dfs = [&](auto&& self, int v, int c) -> int {
            cnt[v] = (h[v] == c);
            for (int u : adj[v]) {
                cnt[v] += self(self, u, c);
            }
            return cnt[v];
        };
        for (int i = 0; i < nn; ++i) {
            dfs(dfs, 0, ff[i]);
            for (int j = 0; j < r; ++j) {
                for (int v : heads[j]) {
                    ans[j][i] += cnt[v];
                }
            }
        }
    }

    for (int r1, r2; q--;) {
        cin >> r1 >> r2;
        --r1, --r2;
        if (f[r2] >= SQ) {
            cout << ans[r1][fi[r2]] << endl;
        } else {
            int i = 0, j = 0;
            int ans = 0;
            while (i != heads[r1].size() && j != all[r2].size()) {
                int v = all[r2][j];
                while (i != heads[r1].size() && out[heads[r1][i]] <= in[v]) {
                    ++i;
                }
                if (i == heads[r1].size()) break;
                int u = heads[r1][i];
                ans += (in[u] <= in[v] && in[v] < out[u]);
                ++j;
            }
            cout << ans << endl;
        }
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             while (i != heads[r1].size() && j != all[r2].size()) {
      |                    ~~^~~~~~~~~~~~~~~~~~~
regions.cpp:84:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |             while (i != heads[r1].size() && j != all[r2].size()) {
      |                                             ~~^~~~~~~~~~~~~~~~~
regions.cpp:86:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |                 while (i != heads[r1].size() && out[heads[r1][i]] <= in[v]) {
      |                        ~~^~~~~~~~~~~~~~~~~~~
regions.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |                 if (i == heads[r1].size()) break;
      |                     ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Incorrect 1 ms 208 KB Output isn't correct
3 Incorrect 3 ms 208 KB Output isn't correct
4 Incorrect 3 ms 208 KB Output isn't correct
5 Incorrect 9 ms 336 KB Output isn't correct
6 Incorrect 19 ms 336 KB Output isn't correct
7 Incorrect 30 ms 336 KB Output isn't correct
8 Incorrect 39 ms 464 KB Output isn't correct
9 Incorrect 44 ms 828 KB Output isn't correct
10 Incorrect 96 ms 1104 KB Output isn't correct
11 Incorrect 105 ms 1644 KB Output isn't correct
12 Incorrect 126 ms 2176 KB Output isn't correct
13 Incorrect 87 ms 2188 KB Output isn't correct
14 Incorrect 185 ms 2872 KB Output isn't correct
15 Incorrect 189 ms 4808 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 780 ms 6900 KB Output isn't correct
2 Incorrect 629 ms 6216 KB Output isn't correct
3 Incorrect 1104 ms 8788 KB Output isn't correct
4 Incorrect 305 ms 3200 KB Output isn't correct
5 Incorrect 302 ms 4768 KB Output isn't correct
6 Incorrect 607 ms 5956 KB Output isn't correct
7 Incorrect 891 ms 7276 KB Output isn't correct
8 Incorrect 990 ms 12032 KB Output isn't correct
9 Incorrect 1375 ms 15092 KB Output isn't correct
10 Incorrect 1850 ms 20152 KB Output isn't correct
11 Incorrect 2284 ms 17712 KB Output isn't correct
12 Incorrect 1078 ms 18668 KB Output isn't correct
13 Incorrect 1226 ms 18456 KB Output isn't correct
14 Incorrect 1803 ms 20544 KB Output isn't correct
15 Incorrect 1779 ms 22992 KB Output isn't correct
16 Incorrect 1988 ms 26112 KB Output isn't correct
17 Incorrect 1746 ms 26248 KB Output isn't correct