oj.uz

Submission #655252

# Submission time Handle Problem Language Result Execution time Memory
655252 2022-11-03T15:48:03 Z d4xn Regions (IOI09_regions) C++17
85 / 100
 8000 ms 27304 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define ii pair<int, int>
#define pb push_back
#define vi vector<int>
#define vvi vector<int>
#define vii vector<ii>

const int N = 200000, R1 = 25000, R2 = 500;

int n, r, q, curr;
int reg[N], sz[N], pre[N], idx[N];
ll ans[R2][R2];
vi adj[N], from[R1], pos[R1];

void dfs(int u) {
  sz[u] = 1;
  pre[curr] = reg[u];
  pos[reg[u]].pb(curr);
  idx[u] = curr;
  curr++;

  for (int &v : adj[u]) {
    dfs(v);
    sz[u] += sz[v];
  }
}

int query(int a, int b, int c) {
  int l = lower_bound(all(pos[c]), a) - pos[c].begin();
  int r = upper_bound(all(pos[c]), b) - pos[c].begin();
  return r-l;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> r >> q;

  for (int i = 0; i < n; i++) {
    if (i) {
      int x;
      cin >> x;
      x--;
      adj[x].pb(i);
    }
  
    cin >> reg[i];
    reg[i]--;
    from[reg[i]].pb(i);
  }

  curr = 0;
  dfs(0);

  if (r <= 500) {
    // precalc all queries
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < r; j++) {
        if (i == j) continue;
        ans[i][j] = 0;
        for (int &u : from[i]) {
          ans[i][j] += query(idx[u], idx[u] + sz[u] - 1, j);
        }
      }
    }
  }

  while (q--) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    if (r <= 500) {
      cout << ans[x][y] << "\n";
      cout.flush();
    }
    else {
      ll cnt = 0;
      for (int &u : from[x]) {
        cnt += query(idx[u], idx[u] + sz[u] - 1, y);
      }
      cout << cnt << "\n";
      cout.flush();
    }   
  }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6224 KB Output is correct
2 Correct 4 ms 6224 KB Output is correct
3 Correct 6 ms 6224 KB Output is correct
4 Correct 7 ms 6268 KB Output is correct
5 Correct 10 ms 6352 KB Output is correct
6 Correct 23 ms 7260 KB Output is correct
7 Correct 35 ms 6812 KB Output is correct
8 Correct 39 ms 7076 KB Output is correct
9 Correct 75 ms 7876 KB Output is correct
10 Correct 197 ms 8328 KB Output is correct
11 Correct 282 ms 8072 KB Output is correct
12 Correct 522 ms 9324 KB Output is correct
13 Correct 563 ms 8620 KB Output is correct
14 Correct 527 ms 8828 KB Output is correct
15 Correct 409 ms 11488 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1566 ms 11860 KB Output is correct
2 Correct 1843 ms 10856 KB Output is correct
3 Correct 2303 ms 13948 KB Output is correct
4 Correct 276 ms 7928 KB Output is correct
5 Correct 184 ms 9552 KB Output is correct
6 Correct 1482 ms 9284 KB Output is correct
7 Correct 1414 ms 10400 KB Output is correct
8 Correct 1281 ms 15556 KB Output is correct
9 Correct 2190 ms 16200 KB Output is correct
10 Correct 4033 ms 21184 KB Output is correct
11 Correct 4574 ms 16280 KB Output is correct
12 Correct 6559 ms 17620 KB Output is correct
13 Correct 7120 ms 17812 KB Output is correct
14 Execution timed out 8003 ms 17668 KB Time limit exceeded
15 Execution timed out 8068 ms 22140 KB Time limit exceeded
16 Correct 7431 ms 27304 KB Output is correct
17 Execution timed out 8025 ms 26092 KB Time limit exceeded