Submission #1033841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033841		vjudge1	Tropical Garden (IOI11_garden)	C11	49 / 100	5092 ms	900 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 graph[150000][2];
  static int sz[150000];
  for (int i = 0; i < M; i++) {
    int u = R[i][0];
    int v = R[i][1];
    if (sz[u] < 2)
      graph[u][sz[u]++] = v;
    if (sz[v] < 2)
      graph[v][sz[v]++] = u;
  }

  for (int i = 0; i < Q; i++) {
    int res = 0;
    for (int j = 0; j < N; j++) {
      int cur = j;
      int prv = -1;
      for (int k = 0; k < G[i]; k++) {
        int old = cur;
        if (prv != graph[cur][0] || sz[cur] <= 1)
          cur = graph[cur][0];
        else
          cur = graph[cur][1];
        prv = old;
      }
      res += cur == P;
    }
    answer(res);
  }
}

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