oj.uz

Submission #1042066

# Submission time Handle Problem Language Result Execution time Memory
1042066 2024-08-02T13:53:03 Z vjudge1 Tropical Garden (IOI11_garden) C++17
69 / 100
 4534 ms 19536 KB 
#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

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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 6 ms 4956 KB Output is correct
12 Correct 15 ms 7000 KB Output is correct
13 Correct 19 ms 13392 KB Output is correct
14 Correct 84 ms 18000 KB Output is correct
15 Correct 81 ms 18256 KB Output is correct
16 Correct 46 ms 13804 KB Output is correct
17 Correct 53 ms 12684 KB Output is correct
18 Correct 44 ms 7000 KB Output is correct
19 Correct 78 ms 18004 KB Output is correct
20 Correct 92 ms 18300 KB Output is correct
21 Correct 132 ms 13956 KB Output is correct
22 Correct 56 ms 12372 KB Output is correct
23 Correct 53 ms 19536 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 6 ms 4956 KB Output is correct
12 Correct 15 ms 7000 KB Output is correct
13 Correct 19 ms 13392 KB Output is correct
14 Correct 84 ms 18000 KB Output is correct
15 Correct 81 ms 18256 KB Output is correct
16 Correct 46 ms 13804 KB Output is correct
17 Correct 53 ms 12684 KB Output is correct
18 Correct 44 ms 7000 KB Output is correct
19 Correct 78 ms 18004 KB Output is correct
20 Correct 92 ms 18300 KB Output is correct
21 Correct 132 ms 13956 KB Output is correct
22 Correct 56 ms 12372 KB Output is correct
23 Correct 53 ms 19536 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 396 ms 5196 KB Output is correct
26 Correct 856 ms 7256 KB Output is correct
27 Correct 1198 ms 13660 KB Output is correct
28 Correct 4534 ms 18124 KB Output is correct
29 Correct 3801 ms 18476 KB Output is correct
30 Correct 2492 ms 13904 KB Output is correct
31 Correct 2183 ms 12628 KB Output is correct
32 Incorrect 940 ms 7004 KB Output isn't correct
33 Halted 0 ms 0 KB -