oj.uz

Submission #317357

# Submission time Handle Problem Language Result Execution time Memory
317357 2020-10-29T15:27:49 Z tushar_2658 Regions (IOI09_regions) C++14
8 / 100
 1471 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]);
      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: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
8.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 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 11 ms 10368 KB Output is correct
5 Correct 15 ms 10496 KB Output is correct
6 Correct 36 ms 10368 KB Output is correct
7 Correct 47 ms 10624 KB Output is correct
8 Correct 49 ms 10624 KB Output is correct
9 Runtime error 33 ms 22904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 67 ms 24176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 109 ms 24824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 103 ms 26232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 180 ms 25208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 351 ms 27024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 142 ms 31352 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 Runtime error 982 ms 33104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 1471 ms 30932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 333 ms 34808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 39 ms 23680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 43 ms 26872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 45 ms 24956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 59 ms 27384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 86 ms 37240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 167 ms 37880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 121 ms 45560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 118 ms 34808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 255 ms 40184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 187 ms 40952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 288 ms 40568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 151 ms 49016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 153 ms 59128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 156 ms 57464 KB Execution killed with signal 11 (could be triggered by violating memory limits)