Submission #317365

#	Time	Username	Problem	Language	Result	Execution time	Memory
317365		tushar_2658	Regions (IOI09_regions)	C++14	100 / 100	6193 ms	45728 KiB

regions

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

const int maxn = 200005;
using ll = long long;

vector<int> edges[maxn];
int a[maxn];
int magic = 320;
vector<int> nodes[maxn];
ll ans[2 + (200000 / 320)][25005];
int cur, node = 0, id[maxn];

void dfs(int x, int p, ll cnt){
  if(a[x] == cur)++cnt;
  else {
    ans[id[cur]][a[x]] += cnt;
  }
  for(auto i : edges[x]){
    if(i != p){
      dfs(i, x, cnt);
    }
  }
}

int st[maxn], ed[maxn], vert[maxn], timer = 0;

void calc(int x, int p){
  st[x] = ++timer;
  vert[timer] = x;
  for(auto i : edges[x]){
    if(i != p){
      calc(i, x);
    }
  }
  ed[x] = timer;
}

vector<int> v[25005];

ll get(int l, int r, int x){
  return upper_bound(v[x].begin(), v[x].end(), r) - lower_bound(v[x].begin(), v[x].end(), l);
}

int main(int argc, char const *argv[])
{
  int n, r, q;
  scanf("%d %d %d", &n, &r, &q);
  scanf("%d", &a[1]);
  for(int i = 2; i <= n; ++i){
    int x;
    scanf("%d %d", &x, &a[i]);
    edges[x].push_back(i);
  }
  vector<int> big(n + 1);
  for(int i = 1; i <= n; ++i){
    nodes[a[i]].push_back(i);
  }
  for(int i = 1; i <= r; ++i){
    if((int)nodes[i].size() > magic){
      big[i] = 1;
      cur = i;
      ++node;  
      id[i] = node;
      dfs(1, 1, 0);
    }
  }
  calc(1, 1);
  for(int i = 1; i <= n; ++i){
    v[a[vert[i]]].push_back(i);
  }
  while(q--){
    int r1, r2;
    scanf("%d %d", &r1, &r2);
    if(big[r1]){
      printf("%lld\n", ans[id[r1]][r2]);
      fflush(stdout);
    }else {
      ll res = 0;
      for(auto i : nodes[r1]){
        res += get(st[i], ed[i], r2);
      }
      printf("%lld\n", res);
      fflush(stdout);
    }
  }

  return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main(int, const char**)':
regions.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   scanf("%d %d %d", &n, &r, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |   scanf("%d", &a[1]);
      |   ~~~~~^~~~~~~~~~~~~
regions.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     scanf("%d %d", &x, &a[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     scanf("%d %d", &r1, &r2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

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