Submission #304698

#	Time	Username	Problem	Language	Result	Execution time	Memory
304698		AlexPop28	Tropical Garden (IOI11_garden)	C++11	69 / 100	5098 ms	49144 KiB

garden

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

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

using namespace std;

void count_routes(int n, int m, int p, int r[][2], int q, int qrs[]) {
  vector<vector<int>> to(n);
  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);
  }
  
  vector<int> nxt(2 * n, -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];
  
  vector<vector<int>> jump(30, vector<int>(2 * n));
  jump[0] = nxt;
  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 = count(pos.begin(), pos.end(), p) + 
              count(pos.begin(), pos.end(), n + p);
    answer(ans);
  }
}

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