oj.uz

Submission #317354

# Submission time Handle Problem Language Result Execution time Memory
317354 2020-10-29T15:26:43 Z tushar_2658 Regions (IOI09_regions) C++14
0 / 100
 656 ms 59128 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;
vector<int> nodes[maxn];
ll ans[200][25005];
int cur;

void dfs(int x, int p, ll cnt){
  if(a[x] == cur)++cnt;
  else {
    ans[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);
  }
  magic = sqrt(r);
  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;
      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[r1][r2]);
    }else {
      ll res = 0;
      for(auto i : nodes[r1]){
        res += get(st[i], ed[i], r2);
      }
      printf("%lld\n", res);
    }
  }

  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:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   73 |     scanf("%d %d", &r1, &r2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6 ms 10368 KB Time limit exceeded (wall clock)
2 Execution timed out 6 ms 10368 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 10368 KB Time limit exceeded (wall clock)
4 Execution timed out 7 ms 10368 KB Time limit exceeded (wall clock)
5 Execution timed out 7 ms 10496 KB Time limit exceeded (wall clock)
6 Execution timed out 7 ms 10368 KB Time limit exceeded (wall clock)
7 Execution timed out 8 ms 10624 KB Time limit exceeded (wall clock)
8 Execution timed out 8 ms 10624 KB Time limit exceeded (wall clock)
9 Runtime error 33 ms 22904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 63 ms 23928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 109 ms 24952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 106 ms 26360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 204 ms 25336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Execution timed out 180 ms 13304 KB Time limit exceeded (wall clock)
15 Runtime error 142 ms 31096 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 370 ms 16752 KB Time limit exceeded (wall clock)
2 Execution timed out 656 ms 15608 KB Time limit exceeded (wall clock)
3 Runtime error 321 ms 34808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 42 ms 23672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 44 ms 27000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 43 ms 24952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 60 ms 27384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 78 ms 37240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 170 ms 37880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 111 ms 45560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 117 ms 34808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 268 ms 40340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 185 ms 40968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 268 ms 40316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 154 ms 49048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 154 ms 59128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 159 ms 57464 KB Execution killed with signal 11 (could be triggered by violating memory limits)