Submission #1042150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042150		izanbf	Tropical Garden (IOI11_garden)	C++14	100 / 100	1260 ms	34132 KiB

garden

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


void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  vector<vector<int>> adj(N);
  for (int i = 0; i < M; ++i) {
    adj[R[i][0]].push_back(R[i][1]);
    adj[R[i][1]].push_back(R[i][0]);
  }

  auto node = [&](int u, int v) {
    if (adj[v][0] == u)
      return N+v;
    else
      return v;
  };

  const int J = 29;
  vector<int> succ(2*N, -1), indeg(2*N, 0);
  vector<vector<int>> rev(2*N);

  auto set_succ = [&](int u, int v) {
    succ[u] = v;
    rev[v].push_back(u);
    ++indeg[v];
  };

  for (int i = 0; i < N; ++i) {
    set_succ(node(-1, i), node(i, adj[i][0]));
    for (int v : adj[i]) {
      if (v != adj[i][0] or adj[i].size() == 1)
        set_succ(node(v, i), node(i, adj[i][0]));
      else
        set_succ(node(v, i), node(i, adj[i][1]));
    }
  }

  vector<int> lambda(2*N, -1), mu(2*N, -1);

  auto floyd_cycle = [&](int u) {
    // buscamos dos elementos en un ciclo
    int a = succ[u];
    int b = succ[succ[u]];
    int i = 1;
    while (a != b) {
      if (mu[a] == 0) break;
      ++i;
      a = succ[a];
      b = succ[succ[b]];
    }

    if (mu[a] == 0) { // este ciclo ya lo hemos completado antes, no queremos repetir
      lambda[u] = lambda[a];
      mu[u] = i;
    }
    else {
      // ahora iteramos el ciclo para calcular su longitud
      b = succ[a];
      lambda[u] = 1; // longitud ciclo
      while (a != b) {
        ++lambda[u];
        b = succ[b];
      }
      // lambda[u] calculada

      // pasamos por todos los elementos del ciclo para guardar la informacion
      for (int i = 0; i < lambda[u]; ++i) {
        mu[a] = 0;
        lambda[a] = lambda[u];
        a = succ[a];
      }

      // reiniciamos punteros y ahora calculamos longitud de la cola e inicio del ciclo
      a = u;
      b = u;
      for (int i = 0; i < lambda[u]; ++i) {
        b = succ[b];
      }
      mu[u] = 0; // longitud cola 
      while (a != b) {
        ++mu[u];
        a = succ[a];
        b = succ[b];
      }
      // mu[u] calculada
    }

    // pasamos por los elementos de la cola para guardar la informacion
    a = succ[u];
    for (int i = 1; i < mu[u]; ++i) {
      mu[a] = mu[u] - i;
      lambda[a] = lambda[u];
      a = succ[a];
    }
  };

  // empezamos a hacer floyd por las hojas, para procesar colas eficientemente
  for (int u = 0; u < 2*N; ++u) {
    if (indeg[u] == 0) floyd_cycle(u);
  }

  // los que queden son ciclos puros
  for (int u = 0; u < 2*N; ++u) {
    if (mu[u] == -1) floyd_cycle(u);
  }

  auto get_rev_dists = [&](int u) {
    vector<int> dist(2*N, -1);
    queue<int> q;
    dist[u] = 0;
    q.push(u);
    while (not q.empty()) {
      int i = q.front(); q.pop();
      for (int j : rev[i]) {
        if (dist[j] == -1) {
          q.push(j);
          dist[j] = dist[i] + 1;
        }
      }
    }
    return dist;
  };

  auto can_reach = [&](int u, int v, int k, const vector<int>& dists) -> bool {
    if (dists[u] == -1) return false; // otra componenete
    if (k < dists[u]) return false; // no llegamos
    if (dists[u] == k) return true; // directamente
    if (mu[v] == 0 and (k - dists[u]) % lambda[v] == 0) // dando vueltas al ciclo
      return true; 
    return false;
  };

  vector<int> distP = get_rev_dists(P), distNP = get_rev_dists(N+P);

  for(int it = 0; it < Q; ++it) {
    int cnt = 0;
    for (int i = 0; i < N; ++i) {
      int u = node(-1, i);

      if (can_reach(u, P, G[it], distP) or can_reach(u, N+P, G[it], distNP))
        ++cnt;
    }

    answer(cnt);
  }
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:21:13: warning: unused variable 'J' [-Wunused-variable]
   21 |   const int J = 29;
      |             ^

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