Submission #1034832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034832		vjudge1	Tropical Garden (IOI11_garden)	C11	69 / 100	5056 ms	40796 KiB

garden

#include "garden.h"
#include "gardenlib.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];
  // 10^9 < 2^30
  static int nxt[30][300001];
  // 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;
    }
  }

  // binary lift
  for (int u = 1; u <= 2 * N; u++)
    nxt[0][u] = graph[u];
  for (int p = 1; p < 30; p++)
    for (int u = 1; u <= 2 * N; u++)
      nxt[p][u] = nxt[p-1][ nxt[p-1][u] ];

  for (int i = 0; i < Q; i++) {
    int res = 0;
    for (int j = 1; j <= N; j++) {
      int u = j;
      for (int p = 0; p < 30; p++)
        if (G[i] >> p & 1)
          u = nxt[p][u];
      res += u == P || u == P + N;
    }
    answer(res);
  }
}

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31