Submission #1135784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135784		m_bezrutchka	Regions (IOI09_regions)	C++20	30 / 100	402 ms	16688 KiB

regions

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN = 2e5 + 10;
const int SQRT = 512;
vector<int> adj[MAXN];
int n, r, q;
int cnt[SQRT];
int tot[SQRT][SQRT], reg[MAXN], sup[MAXN];

void dfs(int v) {
  for (int i = 1; i <= r; i++) {
    tot[i][reg[v]] += cnt[i];
  }
  cnt[reg[v]]++;
  for (int w: adj[v]) {
    dfs(w);
  }
  cnt[reg[v]]--;
}

void solve() {
  cin >> n >> r >> q;
  cin >> reg[1];
  for (int i = 2; i <= n; i++) {
    cin >> sup[i] >> reg[i];
    adj[sup[i]].push_back(i);
  }  
  dfs(1);
  while (q--) {
    int x, y;
    cin >> x >> y;
    cout << tot[x][y] << endl;
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}

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