Submission #738471

#	Time	Username	Problem	Language	Result	Execution time	Memory
738471		lorenzoferrari	Regions (IOI09_regions)	C++17	0 / 100	2284 ms	26248 KiB

regions

#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 (stderr)

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
• Subtask 2: 0 / 85