oj.uz

Submission #317362

# Submission time Handle Problem Language Result Execution time Memory
317362 2020-10-29T15:39:27 Z tushar_2658 Regions (IOI09_regions) C++14
95 / 100
 7173 ms 131072 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 = 200;
vector<int> nodes[maxn];
ll ans[505][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 9 ms 10368 KB Output is correct
2 Correct 7 ms 10368 KB Output is correct
3 Correct 9 ms 10368 KB Output is correct
4 Correct 9 ms 10368 KB Output is correct
5 Correct 15 ms 10368 KB Output is correct
6 Correct 25 ms 10368 KB Output is correct
7 Correct 35 ms 10496 KB Output is correct
8 Correct 39 ms 10496 KB Output is correct
9 Correct 37 ms 10940 KB Output is correct
10 Correct 87 ms 10880 KB Output is correct
11 Correct 136 ms 11264 KB Output is correct
12 Correct 143 ms 11896 KB Output is correct
13 Correct 198 ms 11520 KB Output is correct
14 Correct 336 ms 12160 KB Output is correct
15 Correct 297 ms 14848 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1393 ms 16108 KB Output is correct
2 Correct 1346 ms 15480 KB Output is correct
3 Correct 3216 ms 17528 KB Output is correct
4 Correct 340 ms 12288 KB Output is correct
5 Correct 328 ms 13952 KB Output is correct
6 Correct 587 ms 17272 KB Output is correct
7 Correct 1292 ms 19064 KB Output is correct
8 Correct 1269 ms 28280 KB Output is correct
9 Correct 3034 ms 33144 KB Output is correct
10 Correct 3467 ms 95432 KB Output is correct
11 Runtime error 6608 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 7173 ms 60288 KB Output is correct
13 Correct 4786 ms 61220 KB Output is correct
14 Correct 3215 ms 26244 KB Output is correct
15 Correct 4022 ms 27436 KB Output is correct
16 Correct 4303 ms 130588 KB Output is correct
17 Correct 3364 ms 34808 KB Output is correct