oj.uz

Submission #415187

# Submission time Handle Problem Language Result Execution time Memory
415187 2021-05-31T16:21:05 Z Alex_tz307 Regions (IOI09_regions) C++17
85 / 100
 8000 ms 35524 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5;
const int MAXR = 25 * 1e3;
int r[MAXN], timer, in[MAXN], out[MAXN];
vector<int> G[MAXN], R[MAXR], pos[MAXR];

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

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;
  scanf("%d %d %d", &n, &Q, &Q);
  for (int v = 0; v < n; ++v) {
    if (v == 0) {
      scanf("%d", &r[0]);
      --r[0];
      R[r[0]].emplace_back(0);
      continue;
    }
    int u;
    scanf("%d %d", &u, &r[v]);
    --r[v];
    G[u - 1].emplace_back(v);
    R[r[v]].emplace_back(v);
  }
  dfs(0);
  map<pair<int,int>,int> sol;
  for (int q = 0; q < Q; ++q) {
    int r1, r2;
    scanf("%d %d", &r1, &r2);
    --r1, --r2;
    pair<int,int> p{r1, r2};
    auto it = sol.find(p);
    if (it != sol.end()) {
      printf("%d\n", it->second);
      fflush(stdout);
    }
    else {
      int ans = solve(r1, r2);
      sol[p] = ans;
      printf("%d\n", ans);
      fflush(stdout);
    }
  }
  return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d %d %d", &n, &Q, &Q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:48:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |       scanf("%d", &r[0]);
      |       ~~~~~^~~~~~~~~~~~~
regions.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d %d", &u, &r[v]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
regions.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     scanf("%d %d", &r1, &r2);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6088 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 6 ms 6088 KB Output is correct
4 Correct 8 ms 6088 KB Output is correct
5 Correct 12 ms 6216 KB Output is correct
6 Correct 24 ms 6324 KB Output is correct
7 Correct 38 ms 6336 KB Output is correct
8 Correct 39 ms 6464 KB Output is correct
9 Correct 53 ms 6772 KB Output is correct
10 Correct 104 ms 7108 KB Output is correct
11 Correct 134 ms 7532 KB Output is correct
12 Correct 172 ms 8112 KB Output is correct
13 Correct 242 ms 7968 KB Output is correct
14 Correct 340 ms 8432 KB Output is correct
15 Correct 329 ms 10580 KB Output is correct

Subtask #2
70.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1643 ms 12204 KB Output is correct
2 Correct 1939 ms 11276 KB Output is correct
3 Correct 2531 ms 15948 KB Output is correct
4 Correct 382 ms 9400 KB Output is correct
5 Correct 543 ms 11144 KB Output is correct
6 Correct 702 ms 11020 KB Output is correct
7 Correct 1236 ms 11464 KB Output is correct
8 Correct 1339 ms 18124 KB Output is correct
9 Correct 2868 ms 23440 KB Output is correct
10 Correct 4895 ms 29280 KB Output is correct
11 Correct 5383 ms 27376 KB Output is correct
12 Correct 5749 ms 21896 KB Output is correct
13 Correct 6632 ms 23920 KB Output is correct
14 Execution timed out 8016 ms 24184 KB Time limit exceeded
15 Execution timed out 8029 ms 29956 KB Time limit exceeded
16 Execution timed out 8087 ms 35524 KB Time limit exceeded
17 Correct 7141 ms 34032 KB Output is correct