Submission #837001

#	Time	Username	Problem	Language	Result	Execution time	Memory
837001		thimote75	Tropical Garden (IOI11_garden)	C++14	49 / 100	5053 ms	2080 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

igrid roads;

int createNode (int node, bool cMax) {
  return 2 * node + (cMax ? 1 : 0);
}

idata functional_graph;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
  roads.resize(N);

  for (int i = M - 1; i >= 0; i --) {
    roads[R[i][0]].push_back(R[i][1]);
    roads[R[i][1]].push_back(R[i][0]);
  }

  functional_graph.resize(2 * N);
  for (int i = 0; i < N; i ++) {
    idata &l_roads = roads[i];

    int nmax = l_roads[l_roads.size() - 1];
    int nmix = l_roads[max(0, (int) l_roads.size() - 2)];
    
    functional_graph[2 * i]     = 2 * nmax + (roads[nmax][roads[nmax].size() - 1] == i ? 1 : 0);
    functional_graph[2 * i + 1] = 2 * nmix + (roads[nmix][roads[nmix].size() - 1] == i ? 1 : 0);
  }

  for (int i = 0; i < Q; i ++) {
    int duration = G[i];
    int count    = 0;
    for (int j = 0; j < N; j ++) {
      int x = 2 * j;

      for (int t = 0; t < duration; t ++)
        x = functional_graph[x];

      if (x == 2 * P || x == 2 * P + 1) count ++;
    }

    answer(count);
  }
}

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