Submission #304714

#	Time	Username	Problem	Language	Result	Execution time	Memory
304714		AlexPop28	Tropical Garden (IOI11_garden)	C++11	69 / 100	171 ms	35036 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>> adj(2 * n);
  for (int i = 0; i < 2 * n; ++i) {
    adj[nxt[i]].emplace_back(i);
  }
  
  vector<bool> vis(2 * n);
  
  function<void(int, int , int&, vector<int>&)> 
  DFS = [&](int node, int stop, int &cycle_len, vector<int> &dist) {
    if (vis[node]) {
      if (node == stop) {
        cycle_len = dist[node];
      }
      return;
    }
    
    vis[node] = true;
    for (int &x : adj[node]) {
      dist[x] = 1 + dist[node];
      DFS(x, stop, cycle_len, dist);
    }
  };
  
  const int INF = (int)1e9 + 10;
  vector<int> cycle(2, INF);
  vector<vector<int>> dist(2, vector<int>(2 * n, -1));
  
  dist[0][p] = dist[1][p + n] = 0;
  DFS(p, p, cycle[0], dist[0]);
  fill(vis.begin(), vis.end(), false);
  DFS(p + n, p + n, cycle[1], dist[1]);
  
  vector<vector<int>> cnt_dist(2, vector<int>(2 * n));
  for (int i = 0; i < 2; ++i) {
    for (int node = 0; node < n; ++node) { // doar nodurile "bune" conteaza ca doar din ele pot incepe
      if (dist[i][node] == -1) continue;
      ++cnt_dist[i][dist[i][node]];
    }
  }
  
  for (int it = 0; it < q; ++it) {
    int k = qrs[it];
    int ans = 0;
    for (int i = 0; i < 2; ++i) {
      int kk = k % cycle[i];
      for (int d = kk; d <= n && d <= k; d += cycle[i])
        ans += cnt_dist[i][d];
    }
    answer(ans);
  }
}

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