oj.uz

Submission #317365

# Submission time Handle Problem Language Result Execution time Memory
317365 2020-10-29T15:42:20 Z tushar_2658 Regions (IOI09_regions) C++14
100 / 100
 6193 ms 45728 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10368 KB Output is correct
2 Correct 8 ms 10272 KB Output is correct
3 Correct 12 ms 10368 KB Output is correct
4 Correct 12 ms 10368 KB Output is correct
5 Correct 14 ms 10368 KB Output is correct
6 Correct 18 ms 10368 KB Output is correct
7 Correct 37 ms 10368 KB Output is correct
8 Correct 29 ms 10496 KB Output is correct
9 Correct 56 ms 10880 KB Output is correct
10 Correct 105 ms 10880 KB Output is correct
11 Correct 140 ms 11264 KB Output is correct
12 Correct 189 ms 11776 KB Output is correct
13 Correct 243 ms 11496 KB Output is correct
14 Correct 379 ms 12160 KB Output is correct
15 Correct 322 ms 14848 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2091 ms 15736 KB Output is correct
2 Correct 2979 ms 14456 KB Output is correct
3 Correct 3802 ms 17528 KB Output is correct
4 Correct 402 ms 12180 KB Output is correct
5 Correct 389 ms 13952 KB Output is correct
6 Correct 719 ms 17272 KB Output is correct
7 Correct 1837 ms 18552 KB Output is correct
8 Correct 1365 ms 28340 KB Output is correct
9 Correct 3368 ms 20960 KB Output is correct
10 Correct 3973 ms 45728 KB Output is correct
11 Correct 6193 ms 21240 KB Output is correct
12 Correct 1771 ms 22680 KB Output is correct
13 Correct 2585 ms 22904 KB Output is correct
14 Correct 3577 ms 26252 KB Output is correct
15 Correct 3842 ms 27384 KB Output is correct
16 Correct 3995 ms 32636 KB Output is correct
17 Correct 3450 ms 34804 KB Output is correct