oj.uz

Submission #655238

# Submission time Handle Problem Language Result Execution time Memory
655238 2022-11-03T15:19:47 Z d4xn Regions (IOI09_regions) C++17
30 / 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];
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 22 ms 43088 KB Output is correct
2 Correct 23 ms 43216 KB Output is correct
3 Correct 23 ms 43216 KB Output is correct
4 Correct 24 ms 43272 KB Output is correct
5 Correct 32 ms 43504 KB Output is correct
6 Correct 66 ms 44508 KB Output is correct
7 Correct 57 ms 44368 KB Output is correct
8 Correct 110 ms 44856 KB Output is correct
9 Correct 459 ms 46876 KB Output is correct
10 Correct 593 ms 50004 KB Output is correct
11 Correct 949 ms 51400 KB Output is correct
12 Correct 3723 ms 55548 KB Output is correct
13 Correct 1101 ms 56188 KB Output is correct
14 Correct 1196 ms 57924 KB Output is correct
15 Correct 4200 ms 64276 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8077 ms 74096 KB Time limit exceeded
2 Correct 6718 ms 75156 KB Output is correct
3 Execution timed out 8092 ms 82876 KB Time limit exceeded
4 Correct 1187 ms 60292 KB Output is correct
5 Correct 2064 ms 65352 KB Output is correct
6 Execution timed out 8095 ms 72136 KB Time limit exceeded
7 Execution timed out 8057 ms 87868 KB Time limit exceeded
8 Execution timed out 8038 ms 102320 KB Time limit exceeded
9 Runtime error 241 ms 131072 KB Execution killed with signal 9
10 Runtime error 218 ms 131072 KB Execution killed with signal 9
11 Runtime error 269 ms 131072 KB Execution killed with signal 9
12 Runtime error 256 ms 131072 KB Execution killed with signal 9
13 Runtime error 240 ms 131072 KB Execution killed with signal 9
14 Runtime error 255 ms 131072 KB Execution killed with signal 9
15 Runtime error 239 ms 131072 KB Execution killed with signal 9
16 Runtime error 220 ms 131072 KB Execution killed with signal 9
17 Runtime error 224 ms 131072 KB Execution killed with signal 9