oj.uz

Submission #317364

# Submission time Handle Problem Language Result Execution time Memory
317364 2020-10-29T15:41:46 Z tushar_2658 Regions (IOI09_regions) C++14
95 / 100
 7662 ms 131076 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[2 + (200000 / 200)][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 10496 KB Output is correct
2 Correct 8 ms 10368 KB Output is correct
3 Correct 9 ms 10368 KB Output is correct
4 Correct 13 ms 10368 KB Output is correct
5 Correct 14 ms 10400 KB Output is correct
6 Correct 25 ms 10368 KB Output is correct
7 Correct 38 ms 10368 KB Output is correct
8 Correct 41 ms 10496 KB Output is correct
9 Correct 67 ms 10880 KB Output is correct
10 Correct 89 ms 10880 KB Output is correct
11 Correct 131 ms 11264 KB Output is correct
12 Correct 166 ms 11776 KB Output is correct
13 Correct 214 ms 11552 KB Output is correct
14 Correct 339 ms 12160 KB Output is correct
15 Correct 327 ms 14840 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1465 ms 16120 KB Output is correct
2 Correct 1342 ms 15488 KB Output is correct
3 Correct 3494 ms 17528 KB Output is correct
4 Correct 386 ms 12288 KB Output is correct
5 Correct 394 ms 13952 KB Output is correct
6 Correct 597 ms 17144 KB Output is correct
7 Correct 1378 ms 19064 KB Output is correct
8 Correct 1559 ms 28280 KB Output is correct
9 Correct 3396 ms 33160 KB Output is correct
10 Correct 3874 ms 95380 KB Output is correct
11 Runtime error 7611 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Correct 7662 ms 59988 KB Output is correct
13 Correct 5335 ms 60992 KB Output is correct
14 Correct 3757 ms 26244 KB Output is correct
15 Correct 4866 ms 27384 KB Output is correct
16 Correct 4059 ms 130564 KB Output is correct
17 Correct 3422 ms 34808 KB Output is correct