oj.uz

Submission #839182

# Submission time Handle Problem Language Result Execution time Memory
839182 2023-08-29T02:35:28 Z asdfgrace Tropical Garden (IOI11_garden) C++17
69 / 100
 3523 ms 30648 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
 
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  const int INF = (int) 1e9;
  vector<vector<int>> edges(N);
  for (int i = 0; i < M; ++i) {
    edges[R[i][0]].push_back(R[i][1]);
    edges[R[i][1]].push_back(R[i][0]);
  }
  vector<int> next(2 * N, -1);
  for (int i = 0; i < N; ++i) {
    int x = edges[i][0];
    next[2 * i] = (i == edges[x][0] ? 2 * x + 1 : 2 * x);
    x = ((int) edges[i].size() == 1 ? edges[i][0] : edges[i][1]);
    next[2 * i + 1] = (i == edges[x][0] ? 2 * x + 1 : 2 * x);
  }
  vector<vector<int>> pred(2 * N);
  for (int i = 0; i < 2 * N; ++i) {
    pred[next[i]].push_back(i);
  }
  vector<bool> visited(2 * N, false), active(2 * N, false);
  vector<int> st, cyc_sz(2 * N, 0), cyc_dist(2 * N, INF), elem(2 * N, -1),
    cyc_root(2 * N, -1), cyc_id(2 * N, -1);
  int cycles = -1, start = 0;
  function<void(int)> dfs = [&](int node) {
    if (active[node]) {
      ++cycles;
      int sz = (int) st.size();
      int bgn = 0;
      while (st[bgn] != node) {
        ++bgn;
      }
      sz -= bgn;
      for (int i = bgn; i < (int) st.size(); ++i) {
        cyc_id[st[i]] = i - bgn;
        cyc_sz[st[i]] = sz;
        cyc_dist[st[i]] = 0;
        cyc_root[st[i]] = st[i];
        elem[st[i]] = cycles;
      }
    }
    if (visited[node]) {
      return;
    }
    visited[node] = true;
    active[node] = true;
    st.push_back(node);
    dfs(next[node]);
    active[node] = false;
    st.pop_back();
  };
  function<void(int, int)> tree_dfs = [&](int node, int root) -> void {
    for (auto x : pred[node]) {
      cyc_dist[x] = cyc_dist[node] + 1;
      cyc_root[x] = root;
      elem[x] = elem[root];
      tree_dfs(x, root);
    }
  };
  for (start = 0; start < 2 * N; start += 2) {
    if (!visited[start]) {
      dfs(start);
    }
  }
  for (int i = 0; i < 2 * N; ++i) {
    if (cyc_dist[i] == INF && cyc_dist[next[i]] == 0) {
      cyc_dist[i] = 1;
      cyc_root[i] = i;
      elem[i] = elem[next[i]];
      tree_dfs(i, i);
    }
  }
  for (int j = 0; j < Q; ++j) {
    int k = G[j], cnt = 0;
    for (int i = 0; i < N; ++i) {
      for (int p = 2 * P; p <= 2 * P + 1; ++p) {
        int node = 2 * i, dist = 0;
        if (elem[node] != elem[p]) continue;
        if (cyc_dist[node] != 0 && cyc_dist[p] <= cyc_dist[node]
          && cyc_root[p] == cyc_root[node]) {
          dist = cyc_dist[node] - cyc_dist[p];
          if (dist == k) {
            ++cnt;
          }
          continue;
        } else if (cyc_dist[p] > cyc_dist[node] ||
          (cyc_dist[p] != 0 && cyc_root[p] != cyc_root[node])) {
          continue;
        } else if (cyc_dist[node] != 0) {
          dist += cyc_dist[node];
          node = next[cyc_root[node]];
        }
        dist += (cyc_id[p] >= cyc_id[node] ? cyc_id[p] - cyc_id[node]
          : cyc_sz[node] - cyc_id[node] + cyc_id[p]);
        if (k >= dist && dist % cyc_sz[node] == k % cyc_sz[node]) {
          ++cnt;
        } 
      }
    }
    answer(cnt);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 9 ms 5132 KB Output is correct
12 Correct 21 ms 8088 KB Output is correct
13 Correct 39 ms 30500 KB Output is correct
14 Correct 86 ms 26340 KB Output is correct
15 Correct 84 ms 26552 KB Output is correct
16 Correct 74 ms 18808 KB Output is correct
17 Correct 57 ms 16076 KB Output is correct
18 Correct 22 ms 7804 KB Output is correct
19 Correct 83 ms 26252 KB Output is correct
20 Correct 90 ms 26644 KB Output is correct
21 Correct 83 ms 18792 KB Output is correct
22 Correct 57 ms 16004 KB Output is correct
23 Correct 88 ms 29336 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 9 ms 5132 KB Output is correct
12 Correct 21 ms 8088 KB Output is correct
13 Correct 39 ms 30500 KB Output is correct
14 Correct 86 ms 26340 KB Output is correct
15 Correct 84 ms 26552 KB Output is correct
16 Correct 74 ms 18808 KB Output is correct
17 Correct 57 ms 16076 KB Output is correct
18 Correct 22 ms 7804 KB Output is correct
19 Correct 83 ms 26252 KB Output is correct
20 Correct 90 ms 26644 KB Output is correct
21 Correct 83 ms 18792 KB Output is correct
22 Correct 57 ms 16004 KB Output is correct
23 Correct 88 ms 29336 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 132 ms 5180 KB Output is correct
26 Correct 180 ms 8168 KB Output is correct
27 Correct 3523 ms 30648 KB Output is correct
28 Correct 1191 ms 26312 KB Output is correct
29 Correct 3397 ms 28472 KB Output is correct
30 Correct 2092 ms 20492 KB Output is correct
31 Correct 1933 ms 17660 KB Output is correct
32 Incorrect 768 ms 8448 KB Output isn't correct
33 Halted 0 ms 0 KB -