oj.uz

Submission #655237

# Submission time Handle Problem Language Result Execution time Memory
655237 2022-11-03T15:18:26 Z d4xn Regions (IOI09_regions) C++17
40 / 100
 8000 ms 131072 KB 
#pragma GCC optimize ("Ofast")
#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 = 2e5+5, R1 = 25e3+3, R2 = 5e2+2;

int n, r, q, curr;
int reg[N], sz[N], pre[N], idx[N];
ll ans[R2][R2];
vi adj[N], from[R1];
unordered_map<int, int> seg[N*4];

void build(int p=1, int l=0, int r=n-1) {
  if (l == r) {
    seg[p][pre[l]]++;
    return;
  }

  int mid = (l+r)/2;
  build(p*2, l, mid);
  build(p*2+1, mid+1, r);

  for (int h : {p*2, p*2+1}) {
    for (auto &[x, y] : seg[h]) {
      seg[p][x] += y;
    }
  }
}

int query(int a, int b, int c, int p=1, int l=0, int r=n-1) {
  if (r < a || l > b) return 0;
  if (a <= l && r <= b) {
    auto it = seg[p].find(c);
    return (it == seg[p].end() ? 0 : it->second);
  }

  int mid = (l+r)/2;
  int x = query(a, b, c, p*2, l, mid);
  int y = query(a, b, c, p*2+1, mid+1, r);

  return x+y;
}

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

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

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);
  build();

  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]) {
          //cerr << i << " " << j << " " << u << " " << query(idx[u], idx[u] + sz[u] - 1, j) << endl;
          ans[i][j] += query(idx[u], idx[u] + sz[u] - 1, j);
        }
        //cerr << ans[i][j] << endl;
      }
    }
  }

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 49352 KB Output is correct
2 Correct 29 ms 49488 KB Output is correct
3 Correct 28 ms 49488 KB Output is correct
4 Correct 34 ms 49616 KB Output is correct
5 Correct 36 ms 49872 KB Output is correct
6 Correct 62 ms 50888 KB Output is correct
7 Correct 76 ms 50808 KB Output is correct
8 Correct 97 ms 51332 KB Output is correct
9 Correct 282 ms 53788 KB Output is correct
10 Correct 613 ms 57448 KB Output is correct
11 Correct 815 ms 59612 KB Output is correct
12 Correct 2506 ms 64292 KB Output is correct
13 Correct 1047 ms 65336 KB Output is correct
14 Correct 1120 ms 67836 KB Output is correct
15 Correct 2206 ms 75416 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 6376 ms 90212 KB Output is correct
2 Correct 5657 ms 91824 KB Output is correct
3 Execution timed out 8032 ms 101020 KB Time limit exceeded
4 Correct 936 ms 69756 KB Output is correct
5 Correct 1323 ms 76064 KB Output is correct
6 Correct 6664 ms 84280 KB Output is correct
7 Execution timed out 8054 ms 101960 KB Time limit exceeded
8 Execution timed out 8045 ms 119640 KB Time limit exceeded
9 Runtime error 190 ms 131072 KB Execution killed with signal 9
10 Runtime error 168 ms 131072 KB Execution killed with signal 9
11 Runtime error 184 ms 131072 KB Execution killed with signal 9
12 Runtime error 196 ms 131072 KB Execution killed with signal 9
13 Runtime error 186 ms 131072 KB Execution killed with signal 9
14 Runtime error 189 ms 131072 KB Execution killed with signal 9
15 Runtime error 185 ms 131072 KB Execution killed with signal 9
16 Runtime error 193 ms 131072 KB Execution killed with signal 9
17 Runtime error 166 ms 131072 KB Execution killed with signal 9