Submission #304704

#	Time	Username	Problem	Language	Result	Execution time	Memory
304704		AlexPop28	Tropical Garden (IOI11_garden)	C++11	69 / 100	5092 ms	46840 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

const int N = 150000;

vector<int> to[N];
int nxt[2 * N];
int jump[30][2 * N];

void count_routes(int n, int m, int p, int r[][2], int q, int qrs[]) {
  for (int i = 0; i < m; ++i) {
    int a = r[i][0], b = r[i][1];
    if ((int)to[a].size() < 2) to[a].emplace_back(b);
    if ((int)to[b].size() < 2) to[b].emplace_back(a);
  }
  
  for (int i = 0; i < 2 * n; ++i) nxt[i] = -1;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 2 && j < (int)to[i].size(); ++j) {
      int x = to[i][j];
      int node = (to[x][0] == i) * n + x;
      nxt[j * n + i] = node;
    }
  }
  for (int i = n; i < 2 * n; ++i) if (nxt[i] == -1) nxt[i] = nxt[i - n];

  for (int i = 0; i < 2 * n; ++i) jump[0][i] = nxt[i];
  for (int i = 1; i < 30; ++i) {
    for (int j = 0; j < 2 * n; ++j) {
      jump[i][j] = jump[i - 1][jump[i - 1][j]];
    }
  }
  
  vector<int> pos(n);
  for (int it = 0; it < q; ++it) {
    int k = qrs[it];
    iota(pos.begin(), pos.end(), 0);
    
    for (int bit = 0; k; ++bit) {
      if (!(k & (1 << bit))) continue;
      k ^= 1 << bit;
      for (int i = 0; i < n; ++i) {
        pos[i] = jump[bit][pos[i]];
      }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += pos[i] == p || pos[i] == n + p;
    }
    answer(ans);
  }
}

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