Submission #881674

#TimeUsernameProblemLanguageResultExecution timeMemory
881674sheldonRegions (IOI09_regions)C++14
95 / 100
2620 ms131072 KiB
#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) {
      |             ~~~~~~~~~~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...