Submission #1042066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042066		vjudge1	Tropical Garden (IOI11_garden)	C++17	69 / 100	4534 ms	19536 KiB

garden

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


struct UnionFind {
  vector<int> parent;

  UnionFind(int n) {
    parent.resize(n);
    for (int i = 0; i < n; ++i) {
      parent[i] = i;
    }
  }

  int find(int u) {
    if (parent[u] == u) return u;
    return parent[u] = find(parent[u]);
  }

  void join(int u, int v) {
    parent[find(v)] = find(u);
  }
};


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);
  vector<int> indeg(2*N, 0);

  auto set_succ = [&](int u, int v) {
    succ[u] = v;
    ++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]));
    }
  }

  UnionFind U(2*N);

  // for (int u = 0; u < 2*N; ++u) {
  //   cout << u << " " << succ[u] << endl;
  // }

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

  auto floyd_cycle = [&](int u) {
    // cerr << "floyd " << u << endl;

    // 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];
      cycle[u] = 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];
        cycle[a] = a;
        U.join(a, succ[a]); // guardamos que forman parte del mismo grupo
        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];
      }
      cycle[u] = a;
      // mu[u] y cycle[u] calculados
    }

    // pasamos por los elementos de la cola para guardar la informacion
    if (mu[u] > 1) U.join(u, succ[u]);
    a = succ[u];
    for (int i = 1; i < mu[u]; ++i) {
      mu[a] = mu[u] - i;
      lambda[a] = lambda[u];
      cycle[a] = cycle[u];
      if (mu[a] > 1) U.join(a, succ[a]);
      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);
  }

  // floyd_cycle(5);

  // floyd_cycle(2);

  // for (int u = 0; u < 2*N; ++u) {
  //   cerr << "$ " << u << " " << mu[u] << " " << lambda[u] <<
  //       " " << cycle[u] << endl;
  // }

  // // comprobaciones
  // for (int u = 0; u < 2*N; ++u) {
  //   if (indeg[u] == 0) assert(mu[u] > 0);
  //   assert(mu[u] != -1 and lambda[u] != -1 and cycle[u] != -1);
  //   if (mu[u] == 0) { // esta en un ciclo
  //     assert(cycle[u] == u);
  //     int v = u;
  //     for (int i = 0; i < lambda[u]; ++i) v = succ[v];
  //     assert(v == u);
  //   }
  //   else {
  //     int v = u;
  //     for (int i = 0; i < mu[u]-1; ++i) v = succ[v];
  //     assert(mu[v] == 1);
  //     v = succ[v];
  //     assert(mu[v] == 0);
  //     int w = v;
  //     for (int i = 0; i < lambda[u]; ++i) w = succ[w];
  //     assert(v == w);
  //     assert(cycle[w] == w);
  //   }
  // }

  vector<int> forwardP(lambda[P]+1, -1), forwardNP(lambda[N+P]+1, -1);

  // si P esta en un ciclo calculamos todos los saltos
  if (mu[P] == 0) {
    forwardP[0] = P;
    for (int i = 1; i < lambda[P]; ++i) {
      forwardP[i] = succ[forwardP[i-1]];
    }
  }

  // si N+P esta en un ciclo calculamos todos los saltos
  if (mu[N+P] == 0) {
    forwardNP[0] = N+P;
    for (int i = 1; i < lambda[N+P]; ++i) {
      forwardNP[i] = succ[forwardNP[i-1]];
    }
  }

  // cout << lambda[P] << " " << mu[P] << " " << lambda[N+P] << " " << mu[N+P] << endl;

  auto can_reach = [&](int u, int v, int k, vector<int>& forward) -> bool {
    
    if (mu[u] > 0) { // caso u en una cola
      if (U.find(u) == U.find(v)) { // los dos en la cola
        int dist = mu[u] - mu[v];
        return k == dist;
      }

      if (k < mu[u]) return false; // no podemos llegar al ciclo

      k -= mu[u];
      u = cycle[u];
    }

    // ahora u esta en un ciclo
    if (U.find(u) == U.find(v)) { // ambos en el ciclo
      int dist_inv = (-k%lambda[u] + lambda[u]) % lambda[u];
      return forward[dist_inv] == u;
    }

    return false;
  };

  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], forwardP) or can_reach(u, N+P, G[it], forwardNP))
        ++cnt;

      // for (int j = 0; j < K; ++j) u = succ[u];
      // if (u == P or u == N+P) ++cnt;
    }

    answer(cnt);
  }
}

Compilation message (stderr)

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

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