Submission #1334538

#TimeUsernameProblemLanguageResultExecution timeMemory
1334538vyaductRegions (IOI09_regions)C++20
0 / 100
47 ms34244 KiB
#include<bits/stdc++.h>
using namespace std;

#define REP(i, from, to) for (ll i=(from);i<=(to);++i)
#define PER(i, from, to) for (ll i=(from);i>=(to);--i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (ll)(x).size()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
 
void solve(){
  int n,r,q; cin>>n>>r>>q;
  vector<vector<int>> Tree(n);
  vector<multiset<int>> reg(n);
  vector<int> h(n);
  cin>>h[0]; h[0]--; reg[0].insert(h[0]);
  REP(i, 1, n-1) {
    int par; cin>>par; par--;
    Tree[par].PB(i);
    Tree[i].PB(par);
    cin>>h[i]; h[i]--; reg[i].insert(h[i]);
  }
  vector<array<int, 4>> qr(q);
  REP(i, 0, q-1) {
    cin>>qr[i][0]>>qr[i][1];
    qr[i][0]--; qr[i][1]--;
    qr[i][2] = i; qr[i][3] = 0;
  }
  sort(ALL(qr));

  auto dfs = [&](auto &&dfs, int v, int par) -> void {
    for (int u : Tree[v]){
      if (u == par) continue;
      dfs(dfs, u, v);
      if (reg[u].size() > reg[v].size()) swap(reg[u], reg[v]);
      for (int x : reg[u]) reg[v].insert(x);
    }
    REP(i, 0, q-1){
      if (qr[i][0] == h[v]){
        qr[i][3] += reg[v].count(qr[i][1]);
      }
    }
  };

  dfs(dfs, 0, -1);
  vector<int> ans(q);
  REP(i, 0, q-1) ans[qr[i][2]] = qr[i][3];

  REP(i, 0, q-1) cout << ans[i] << endl;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt=1;
  // cin>>tt;
  while(tt--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...