Submission #1205765

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205765		shangkuei	Tropical Garden (IOI11_garden)	C++20	0 / 100	1 ms	576 KiB

garden

#include "garden.h"

#include <bits/stdc++.h>

#include "gardenlib.h"
using namespace std;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  // build graph
  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 p, int u) {
    if (p == adj[u][0]) return N + u;
    return u;
  };

  // build functional graph
  vector<int> next(2 * N, -1), ideg(2 * N, 0);
  vector<vector<int>> prev(2 * N);

  auto connect = [&](int u, int v) {
    ideg[v]++;
    next[u] = v;
    prev[v].push_back(u);
  };

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

  // t + c
  vector<int> floydT(2 * N, -1), floydC(2 * N, -1);
  auto floyd = [&](int u) {
    int fast = u, slow = u;
    int len = 0;
    while (true) {
      len++;
      fast = next[next[fast]];
      slow = next[slow];
      if (fast == slow) break;
      if (floydC[slow] != -1) break;
    }

    if (floydC[slow] != -1) {
      fast = u;
      for (int i = 0; i < len; i++) {
        floydC[fast] = floydC[slow];
        floydT[fast] = floydT[slow] + len - i;
        fast = next[fast];
      }
      return;
    }

    int c = 0;
    while (true) {
      c++;
      fast = next[fast];
      if (fast == slow) break;
    }

    fast = u;
    for (int i = 0; i < c; i++) {
      floydC[slow] = c;
      floydT[slow] = 0;
      slow = next[slow];
      fast = next[fast];
    }

    int t = 0;
    slow = u;
    while (true) {
      t++;
      slow = next[slow];
      fast = next[fast];
      if (fast == slow) break;
    }

    slow = u;
    for (int i = 0; i < t; i++) {
      floydC[slow] = c;
      floydT[slow] = t - i;
      slow = next[slow];
    }
  };

  for (int i = 0; i < N; i++) {
    if (ideg[i] == 0 || floydC[i] == -1) floyd(i);
  }

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

  auto reachable = [&](int u, int v, int k, const vector<int>& dist) {
    if (dist[u] == -1) return false;
    if (dist[u] == k) return true;
    if (floydT[v] == 0 && k > dist[u] && (k - dist[u]) % floydC[v] == 0)
      return true;
    return false;
  };

  vector<int> distP = dist(P), distNP = dist(N + P);
  for (int i = 0; i < Q; i++) {
    int cnt = 0;
    for (int j = 0; j < N; j++) {
      if (reachable(j, P, G[i], distP) || reachable(j, N + P, G[i], distNP))
        cnt++;
    }
    answer(cnt);
  }
}

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