Submission #1035922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035922		vjudge1	Tropical Garden (IOI11_garden)	C11	100 / 100	1876 ms	8740 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <stdbool.h>
#include <assert.h>

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] = { 1e9 + 1, 1e9 + 1 };
  static int stack[300000];
  int sz = 0;
  // 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 u = 1; u <= N; u++) {
    if (graph[u] == 0) continue;
    if (rem[0][u] != 0 || u == P) {
      assert(rem[1][u] != 0 || u == P || u == P + N);
      continue;
    }

    int idx[2] = { -1, -1 };
    int v = u;
    while (rem[0][v] == 0 && rem[1][v] == 0) {
      rem[0][v] = rem[1][v] = -1;
      if (v == P) idx[0] = sz;
      else if (v == P + N) idx[1] = sz;
      stack[sz++] = v;
      v = graph[v];
    }

    int cyc_idx = -1;
    while (++cyc_idx < sz && stack[cyc_idx] != v);

    if (cyc_idx < sz) {
      // cycle found
      int c = sz - cyc_idx;
      for (int i = 0; i < 2; i++) {
        if (idx[i] == -1) continue;
        if (idx[i] >= cyc_idx) {
          // part of cycle
          cyc[i] = c;
          for (int j = 1; j + idx[i] < sz; j++)
            rem[i][ stack[j + idx[i]] ] = c - j;
        }
      }
    } else {
      // no cycle
      for (int i = 0; i < 2; i++) {
        if (rem[i][v] != -1)
          for (int j = idx[i] + 1; j < sz; j++)
            rem[i][ stack[j] ] = sz - j + rem[i][v];
      }
    }
    for (int i = 0; i < 2; i++)
      for (int j = 0; j <= idx[i]; j++)
        rem[i][ stack[j] ] = idx[i] - j;
    sz = 0;
  }

  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