제출 #1035203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1035203		vjudge1	열대 식물원 (Tropical Garden) (IOI11_garden)	C11	100 / 100	1804 ms	6228 KiB

garden

#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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31