oj.uz

Submission #1035203

# Submission time Handle Problem Language Result Execution time Memory
1035203 2024-07-26T06:32:47 Z vjudge1 Tropical Garden (IOI11_garden) C
100 / 100
 1804 ms 6228 KB 
#include "garden.h"
#include "gardenlib.h"
#include <stdbool.h>
#include <assert.h>

void floyds(const int *G, int u, int v, /*out*/ int *cyc, /*out*/ int *rem) {
  assert(rem[u] == 0 && u != v);

  bool seen = false;
  int d = 0;
  int slo = u, fas = u;
  do {
    slo = G[slo];
    fas = G[G[fas]];
    if (!seen) d++;
    if (rem[slo] != 0) {
      if (seen) {
        for (; u != G[v]; u = G[u])
          rem[u] = d--;
        assert(d == -1);
      }
      for (; u != slo; u = G[u]) {
        if (rem[slo] == -1)
          rem[u] = -1;
        else
          rem[u] = rem[slo] + d--;
      }
      assert(seen || rem[slo] == -1 || d == 0);
      return;
    }
    rem[slo] = -1;
    seen = seen || slo == v;
  } while (slo != fas);

  rem[u] = -1;

  int c = 0;
  bool in_cyc = false;
  do {
    slo = G[slo];
    rem[slo] = -1;
    seen = seen || slo == v;
    in_cyc = in_cyc || slo == v;
    c++;
  } while (slo != fas);

  if (in_cyc) {
    *cyc = c;
    slo = G[v];
    for (int i = 1; i <= c; i++) {
      rem[slo] = c - i;
      slo = G[slo];
    }
    assert(slo == G[v]);
  }

  if (seen) {
    // find start of cycle and distance to start of cycle
    d = 0;
    slo = u;
    for (; slo != fas; slo = G[slo], fas = G[fas])
      d++;

    for (; u != slo; u = G[u])
      rem[u] = rem[slo] + d--;
    assert(d == 0);
  }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  static int most_beautiful[150001][2];
  static int graph[300001];
  static int rem[2][300001];
  int cyc[2];
  cyc[0] = cyc[1] = 1e9 + 1;
  // 1 indexing, graph[u] == 0, means no edges connected to it
  P++;

  // save 2 most_beautiful edges
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < 2; j++) {
      int u = R[i][j] + 1;
      int v = R[i][j^1] + 1;
      if (most_beautiful[u][0] == 0) {
        most_beautiful[u][0] = v;
      } else if (most_beautiful[u][1] == 0) {
        most_beautiful[u][1] = v;
      }
    }
  }

  // build functional graph
  for (int u = 1; u <= N; u++) {
    for (int j = 0; j < 2; j++) {
      int v = most_beautiful[u][j];
      if (most_beautiful[v][0] != u || most_beautiful[v][1] == 0)
        graph[u + j*N] = v;
      else
        graph[u + j*N] = v + N;
    }
  }

  for (int i = 0; i < 2; i++)
    for (int j = 1; j <= N; j++)
      if (rem[i][j] == 0 && j != P + i*N)
        floyds(graph, j, P + i*N, cyc + i, rem[i]);

  for (int i = 0; i < Q; i++) {
    int res = 0;
    for (int j = 0; j < 2; j++) {
      for (int k = 1; k <= N; k++) {
        if (rem[j][k] == -1) continue;
        res += rem[j][k] <= G[i] && (G[i] - rem[j][k]) % cyc[j] == 0;
      }
    }
    answer(res);
  }
}

Subtask #1
49.0 / 49.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 7 ms 1624 KB Output is correct
13 Correct 14 ms 3676 KB Output is correct
14 Correct 20 ms 4616 KB Output is correct
15 Correct 21 ms 4696 KB Output is correct
16 Correct 18 ms 3664 KB Output is correct
17 Correct 17 ms 3164 KB Output is correct
18 Correct 8 ms 1880 KB Output is correct
19 Correct 22 ms 5724 KB Output is correct
20 Correct 22 ms 5648 KB Output is correct
21 Correct 20 ms 4180 KB Output is correct
22 Correct 21 ms 3676 KB Output is correct
23 Correct 22 ms 5204 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 7 ms 1624 KB Output is correct
13 Correct 14 ms 3676 KB Output is correct
14 Correct 20 ms 4616 KB Output is correct
15 Correct 21 ms 4696 KB Output is correct
16 Correct 18 ms 3664 KB Output is correct
17 Correct 17 ms 3164 KB Output is correct
18 Correct 8 ms 1880 KB Output is correct
19 Correct 22 ms 5724 KB Output is correct
20 Correct 22 ms 5648 KB Output is correct
21 Correct 20 ms 4180 KB Output is correct
22 Correct 21 ms 3676 KB Output is correct
23 Correct 22 ms 5204 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 70 ms 1116 KB Output is correct
26 Correct 120 ms 1624 KB Output is correct
27 Correct 639 ms 3780 KB Output is correct
28 Correct 662 ms 4700 KB Output is correct
29 Correct 774 ms 4716 KB Output is correct
30 Correct 466 ms 3672 KB Output is correct
31 Correct 448 ms 3340 KB Output is correct
32 Correct 121 ms 1884 KB Output is correct
33 Correct 667 ms 5756 KB Output is correct
34 Correct 737 ms 5972 KB Output is correct
35 Correct 916 ms 4184 KB Output is correct
36 Correct 764 ms 3676 KB Output is correct
37 Correct 552 ms 5208 KB Output is correct
38 Correct 1804 ms 6228 KB Output is correct