Submission #839171

#	Time	Username	Problem	Language	Result	Execution time	Memory
839171		asdfgrace	Tropical Garden (IOI11_garden)	C++17	69 / 100	5031 ms	50368 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  const int LOG = 31;
  vector<vector<int>> edges(N);
  for (int i = 0; i < M; ++i) {
    edges[R[i][0]].push_back(R[i][1]);
    edges[R[i][1]].push_back(R[i][0]);
  }
  vector<int> next(2 * N, -1);
  for (int i = 0; i < N; ++i) {
    int x = edges[i][0];
    next[2 * i] = (i == edges[x][0] ? 2 * x + 1 : 2 * x);
    x = ((int) edges[i].size() == 1 ? edges[i][0] : edges[i][1]);
    next[2 * i + 1] = (i == edges[x][0] ? 2 * x + 1 : 2 * x);
  }
  vector<vector<int>> lift(LOG, vector<int>(2 * N));
  lift[0] = next;
  for (int j = 1; j < LOG; ++j) {
    for (int i = 0; i < 2 * N; ++i) {
      lift[j][i] = lift[j - 1][lift[j - 1][i]];
    }
  }
  auto get = [&](int i, int k) {
    for (int j = LOG - 1; j >= 0; --j) {
      if (k >= 1 << j) {
        i = lift[j][i];
        k -= 1 << j;
      }
    }
    return i;
  };
  for (int j = 0; j < Q; ++j) {
    int k = G[j], cnt = 0;
    for (int i = 0; i < N; ++i) {
      if (get(i * 2, k) / 2 == P) ++cnt;
    }
    answer(cnt);
  }
}

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