Submission #881674

#	Time	Username	Problem	Language	Result	Execution time	Memory
881674		sheldon	Regions (IOI09_regions)	C++14	95 / 100	2620 ms	131072 KiB

regions

#include <bits/stdc++.h>

using namespace std;

const int nax = 2e5 + 5;

int region[nax];
vector<int> edges[nax], positions[nax];
int tin[nax], tout[nax], who[nax];
int timer = 0;
unordered_map<int, int> mp[25005];

void dfs (int u, int p) {
    tin[u] = ++timer;
    who[timer] = u;
    positions[region[u]].push_back(timer);
    for (int v : edges[u]) {
        if (v != p) {
            dfs (v, u);
        }
    }
    tout[u] = timer;
}

void solve() {
    int n, r, q;
    cin >> n >> r >> q;
    cin >> region[1];
    for (int i = 2; i <= n; ++i) {
        int p;
        cin >> p >> region[i];
        edges[i].push_back(p);
        edges[p].push_back(i);
    }
    dfs (1, 0);
    const int B = sqrt(n);
    for (int reg = 1; reg <= r; ++reg) {
        if (positions[reg].size() >= B) {
            vector<int> pref(n + 2);
            for (int i = 1; i <= n; ++i) {
                if (region[who[i]] == reg) {
                    pref[i + 1]++;
                    pref[tout[who[i]] + 1]--;
                }
            }
            for (int i = 1; i <= n; ++i) {
                pref[i] += pref[i - 1];
                mp[reg][region[who[i]]] += pref[i];
            }
        }
    }
    while (q--) {
        int reg1, reg2;
        cin >> reg1 >> reg2;
        if (positions[reg1].size() >= B) {
            cout << mp[reg1][reg2] << endl;
        } else {
            int ans = 0;
            for (int i : positions[reg1]) {
                if (region[who[i]] == reg1) {
                    auto it1 = upper_bound(positions[reg2].begin(), positions[reg2].end(), tout[who[i]]) - positions[reg2].begin();
                    auto it2 = lower_bound(positions[reg2].begin(), positions[reg2].end(), i) - positions[reg2].begin();
                    if (it1 != 0) {
                        ans += it1 - it2;
                    }
                }
            }
            cout << ans << endl;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message (stderr)

regions.cpp: In function 'void solve()':
regions.cpp:38:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   38 |         if (positions[reg].size() >= B) {
      |             ~~~~~~~~~~~~~~~~~~~~~~^~~~
regions.cpp:55:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   55 |         if (positions[reg1].size() >= B) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~

• Subtask 1: 15 / 15
• Subtask 2: 80 / 85