oj.uz

Submission #317360

# Submission time Handle Problem Language Result Execution time Memory
317360 2020-10-29T15:30:58 Z tushar_2658 Regions (IOI09_regions) C++14
75 / 100
 5549 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[205][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 8 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 23 ms 10368 KB Output is correct
7 Correct 32 ms 10368 KB Output is correct
8 Correct 43 ms 10496 KB Output is correct
9 Correct 59 ms 11040 KB Output is correct
10 Correct 82 ms 10880 KB Output is correct
11 Correct 104 ms 11264 KB Output is correct
12 Correct 163 ms 11896 KB Output is correct
13 Correct 223 ms 11520 KB Output is correct
14 Correct 349 ms 12160 KB Output is correct
15 Correct 283 ms 14848 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1745 ms 16088 KB Output is correct
2 Correct 1309 ms 15480 KB Output is correct
3 Correct 3680 ms 17532 KB Output is correct
4 Correct 332 ms 12288 KB Output is correct
5 Correct 435 ms 13952 KB Output is correct
6 Correct 636 ms 17272 KB Output is correct
7 Correct 1387 ms 19064 KB Output is correct
8 Correct 1157 ms 28408 KB Output is correct
9 Correct 3233 ms 33404 KB Output is correct
10 Runtime error 814 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 3095 ms 115988 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 5549 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 2749 ms 92512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 2974 ms 26244 KB Output is correct
15 Correct 3614 ms 27432 KB Output is correct
16 Runtime error 1077 ms 131072 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Correct 3251 ms 34808 KB Output is correct