oj.uz

Submission #415243

# Submission time Handle Problem Language Result Execution time Memory
415243 2021-05-31T17:59:33 Z Alex_tz307 Regions (IOI09_regions) C++17
25 / 100
 8000 ms 47900 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5;
const int MAXR = 25 * 1e3;
const int BLOCK = 450;
int m, r[MAXN], timer, in[MAXN], out[MAXN], cnt_large, ind[MAXR], dp[MAXR], root[BLOCK][MAXR], child[BLOCK][MAXR];
vector<int> G[MAXN], R[MAXR], pos[MAXR], S;
bitset<MAXN> is_large;

void dfs1(int u) {
  in[u] = ++timer;
  pos[r[u]].emplace_back(in[u]);
  for (int v : G[u])
    dfs1(v);
  out[u] = timer;
}

void dfs2(int u) {
  for (int region : S)
    ++root[ind[region]][r[u]];
  if (is_large[r[u]]) {
    for (int i = 0; i < m; ++i)
      child[ind[r[u]]][i] += dp[i];
    S.emplace_back(r[u]);
  }
  ++dp[r[u]];
  for (int v : G[u])
    dfs2(v);
  if (is_large[r[u]])
    S.pop_back();
  --dp[r[u]];
}

int solve(int r1, int r2) {
  int ans = 0;
  for (int u : R[r1]) {
    int n = pos[r2].size();
    int st = n, dr = n, l = 0, r = n - 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (in[u] <= pos[r2][mid]) {
        st = mid;
        r = mid - 1;
      } else l = mid + 1;
    }
    l = 0, r = n - 1;
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (out[u] < pos[r2][mid]) {
        dr = mid;
        r = mid - 1;
      } else l = mid + 1;
    }
    ans += dr - st;
  }
  return ans;
}

int main() {
  int n, Q;
  cin >> n >> m >> Q;
  for (int v = 0; v < n; ++v) {
    if (v == 0) {
      cin >> r[0];
      --r[0];
      R[r[0]].emplace_back(0);
      continue;
    }
    int u;
    cin >> u >> r[v];
    --r[v];
    G[u - 1].emplace_back(v);
    R[r[v]].emplace_back(v);
  }
  dfs1(0);
  for (int i = 0; i < m; ++i)
    /* if ((int)R[i].size() > BLOCK) */ {
      is_large[i] = true;
      ind[i] = cnt_large++;
    }
  dfs2(0);
  map<pair<int,int>,int> sol;
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    cin >> r1 >> r2;
    --r1, --r2;
    if ((int)R[r1].size() > BLOCK)
      cout << root[ind[r1]][r2] << '\n';
    else if ((int)R[r2].size() > BLOCK)
      cout << child[ind[r2]][r1] << '\n';
    else {
      pair<int,int> p{r1, r2};
      auto it = sol.find(p);
      if (it != sol.end())
        cout << it->second << '\n';
      else {
        int ans = solve(r1, r2);
        sol[p] = ans;
        cout << ans << '\n';
      }
    }
    cout.flush();
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6216 KB Output is correct
2 Correct 5 ms 6216 KB Output is correct
3 Correct 6 ms 6368 KB Output is correct
4 Correct 9 ms 6472 KB Output is correct
5 Correct 15 ms 6640 KB Output is correct
6 Correct 47 ms 8864 KB Output is correct
7 Correct 47 ms 7836 KB Output is correct
8 Correct 46 ms 8432 KB Output is correct
9 Correct 162 ms 10260 KB Output is correct
10 Correct 112 ms 12020 KB Output is correct
11 Correct 235 ms 10364 KB Output is correct
12 Correct 540 ms 13696 KB Output is correct
13 Correct 264 ms 11676 KB Output is correct
14 Correct 354 ms 10520 KB Output is correct
15 Correct 6287 ms 14504 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 4938 ms 14688 KB Output is correct
2 Correct 2150 ms 13352 KB Output is correct
3 Execution timed out 8036 ms 16012 KB Time limit exceeded
4 Runtime error 46 ms 15680 KB Execution killed with signal 11
5 Runtime error 49 ms 18160 KB Execution killed with signal 11
6 Runtime error 70 ms 18112 KB Execution killed with signal 11
7 Runtime error 89 ms 20292 KB Execution killed with signal 11
8 Runtime error 121 ms 28388 KB Execution killed with signal 11
9 Runtime error 182 ms 31064 KB Execution killed with signal 11
10 Runtime error 176 ms 38880 KB Execution killed with signal 11
11 Runtime error 204 ms 31440 KB Execution killed with signal 11
12 Runtime error 225 ms 33896 KB Execution killed with signal 11
13 Runtime error 203 ms 33852 KB Execution killed with signal 11
14 Runtime error 245 ms 33984 KB Execution killed with signal 11
15 Runtime error 242 ms 40976 KB Execution killed with signal 11
16 Runtime error 204 ms 47900 KB Execution killed with signal 11
17 Runtime error 203 ms 46188 KB Execution killed with signal 11