Submission #1184222

#TimeUsernameProblemLanguageResultExecution timeMemory
1184222GGOSHABRegions (IOI09_regions)C++20
35 / 100
3323 ms46716 KiB
#ifdef ONPC #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> #ifndef ONPC #pragma GCC target("avx") #pragma GCC target("popcnt") #define cerr if (false) cerr #endif using namespace std; #define all(v) begin(v), end(v) #define watch(x) cerr << #x << ": " << x << endl; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> Pint; typedef pair<ll, ll> Pll; mt19937_64 gen64(chrono::steady_clock::now().time_since_epoch().count()); inline ll rnd(ll l = LLONG_MIN, ll r = LLONG_MAX) { return uniform_int_distribution<ll>(l, r)(gen64); } template<class T> bool umin(T &a, const T &b) { return (a > b ? a = b, true : false); } template<class T> bool umax(T &a, const T &b) { return (a < b ? a = b, true : false); } const int mod = 1e9 + 7; ll mult(ll a, ll b) { return (a * b) % mod; } template<class T> void add(T &a, const T &b) { a = (a + b) % mod; } const int inf = int(1e9) + 10; const ll INF = ll(1e18) + 10; const int maxn = 2e5 + 5, maxr = 25000 + 5; constexpr int W = 400; ll prc[maxn / W + 10][maxr]; using state = map<int, ll>; void merge(state &a, state &b) { if (a.size() < b.size()) { swap(a, b); } for (auto [c, f] : b) { a[c] += f; } } vector<int> g[maxn]; int c[maxn], f[maxr]; int idx[maxr], tin[maxn], tout[maxn], timer = 0; void dfs(int v = 1, int p = -1) { tin[v] = ++timer; state cur; for (int u : g[v]) { if (u != p) { dfs(u, v); } } tout[v] = timer; } void stupid(int x, int v = 1, int p = -1, int d = 0) { prc[idx[x]][c[v]] += d; d += (c[v] == x); for (int u : g[v]) { if (u != p) { stupid(x, u, v, d + 1); } } } void solve() { int n, r, q; cin >> n >> r >> q; vector<vector<int>> a(r + 1); for (int v = 1; v <= n; ++v) { if (v != 1) { int p; cin >> p; g[p].push_back(v); } cin >> c[v]; c[v]--; f[c[v]]++; a[c[v]].push_back(v); } int cur = 0; dfs(); for (int x = 0; x < r; ++x) { if (f[x] > W) { idx[x] = cur++; stupid(x); } } vector<int> euler(n + 1); for (int v = 1; v <= n; ++v) { euler[tin[v]] = c[v]; } vector<vector<int>> b(r); for (int i = 1; i <= n; ++i) { b[euler[i]].push_back(i); } while (q--) { int r1, r2; cin >> r1 >> r2; r1--, r2--; if (f[r1] > W) { cout << prc[idx[r1]][r2] << endl; } else { ll ans = 0; for (int v : a[r1]) { ans += upper_bound(all(b[r2]), tout[v]) - lower_bound(all(b[r2]), tin[v]); } cout << ans << endl; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...