Submission #103375

#	Time	Username	Problem	Language	Result	Execution time	Memory
103375		wxh010910	Tropical Garden (IOI11_garden)	C++17	100 / 100	148 ms	32848 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  vector<int> deg(N);
  vector<int> most(N, -1);
  for (int i = 0; i < M; ++i) {
    for (int j = 0; j < 2; ++j) {
      ++deg[R[i][j]];
      if (most[R[i][j]] == -1) {
        most[R[i][j]] = i;
      }
    }
  }
  vector<int> to(N * 2, -1);
  for (int i = 0; i < M; ++i) {
    for (int j = 0; j < 2; ++j) {
      if (to[R[i][j]] == -1) {
        to[R[i][j]] = R[i][!j] + N * (most[R[i][!j]] == i && deg[R[i][!j]] > 1);
      } else if (to[R[i][j] + N] == -1) {
        to[R[i][j] + N] = R[i][!j] + N * (most[R[i][!j]] == i && deg[R[i][!j]] > 1);
      }
    }
  }
  vector<vector<int>> adj(N * 2);
  for (int i = 0; i < N; ++i) {
    adj[to[i]].push_back(i);
    if (deg[i] > 1) {
      adj[to[i + N]].push_back(i + N);
    }
  }
  vector<pair<int, int>> queries(Q);
  for (int i = 0; i < Q; ++i) {
    queries[i] = make_pair(G[i], i);
  }
  sort(queries.begin(), queries.end());
  vector<int> ans(Q);
  auto solve = [&](int source) {
    vector<int> depth(N * 2, -1);
    function<void(int)> dfs = [&](int x) {
      for (auto y : adj[x]) {
        if (depth[y] == -1) {
          depth[y] = depth[x] + 1;
          dfs(y);
        }
      }
    };
    depth[source] = 0;
    dfs(source);
    vector<int> dists;
    for (int i = 0; i < N; ++i) {
      if (depth[i] != -1) {
        dists.push_back(depth[i]);
      }
    }
    sort(dists.begin(), dists.end());
    int cycle = 0;
    vector<bool> visit(N * 2);
    int u = source;
    while (!visit[u]) {
      visit[u] = true;
      u = to[u];
      ++cycle;
    }
    if (u != source) {
      cycle = -1;
    }
    vector<int> cnt(N * 2);
    for (int i = 0, j = 0; i < Q; ++i) {
      while (j < (int) dists.size() && dists[j] <= queries[i].first) {
        if (cycle == -1) {
          ++cnt[dists[j]];
        } else {
          ++cnt[dists[j] % cycle];
        }
        ++j;
      }
      if (cycle == -1) {
        if (queries[i].first < N * 2) {
          ans[queries[i].second] += cnt[queries[i].first];
        }
      } else {
        ans[queries[i].second] += cnt[queries[i].first % cycle];
      }
    }
  };
  solve(P);
  if (deg[P] > 1) {
    solve(P + N);
  }
  for (int i = 0; i < Q; ++i) {
    answer(ans[i]);
  }
}

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