oj.uz

Submission #317361

# Submission time Handle Problem Language Result Execution time Memory
317361 2020-10-29T15:33:13 Z tushar_2658 Regions (IOI09_regions) C++14
75 / 100
 5818 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[255][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 10368 KB Output is correct
3 Correct 9 ms 10368 KB Output is correct
4 Correct 12 ms 10368 KB Output is correct
5 Correct 15 ms 10368 KB Output is correct
6 Correct 26 ms 10496 KB Output is correct
7 Correct 34 ms 10368 KB Output is correct
8 Correct 43 ms 10496 KB Output is correct
9 Correct 57 ms 10944 KB Output is correct
10 Correct 86 ms 10880 KB Output is correct
11 Correct 135 ms 11264 KB Output is correct
12 Correct 169 ms 11896 KB Output is correct
13 Correct 208 ms 11520 KB Output is correct
14 Correct 328 ms 12160 KB Output is correct
15 Correct 313 ms 14848 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1568 ms 16120 KB Output is correct
2 Correct 1222 ms 15480 KB Output is correct
3 Correct 3509 ms 17532 KB Output is correct
4 Correct 313 ms 12288 KB Output is correct
5 Correct 404 ms 13952 KB Output is correct
6 Correct 638 ms 17144 KB Output is correct
7 Correct 1325 ms 19064 KB Output is correct
8 Correct 1313 ms 28280 KB Output is correct
9 Correct 3199 ms 33420 KB Output is correct
10 Runtime error 1008 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 3591 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 5818 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 3405 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Correct 2976 ms 26360 KB Output is correct
15 Correct 3996 ms 27428 KB Output is correct
16 Runtime error 1356 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Correct 3296 ms 34968 KB Output is correct