Submission #231831

#	Time	Username	Problem	Language	Result	Execution time	Memory
231831		IOrtroiii	Tropical Garden (IOI11_garden)	C++14	100 / 100	129 ms	26236 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<int> deg(N);
   vector<int> best(N, -1);
   for (int i = 0; i < M; ++i) {
      for (int z = 0; z < 2; ++z) {
         ++deg[R[i][z]];
         if (best[R[i][z]] == -1) best[R[i][z]] = i;
      }
   }
   vector<int> nxt(N * 2, -1);
   for (int i = 0; i < M; ++i) {
      for (int z = 0; z < 2; ++z) {
         int to = R[i][!z];
         if (best[R[i][!z]] == i && deg[R[i][!z]] > 1) to += N;
         if (nxt[R[i][z]] == -1) nxt[R[i][z]] = to;
         else if (nxt[R[i][z] + N] == -1) nxt[R[i][z] + N] = to;
      }
   }
   vector<vector<int>> adj(2 * N);
   for (int i = 0; i < N; ++i) {
      adj[nxt[i]].emplace_back(i);
      if (deg[i] > 1) adj[nxt[i + N]].emplace_back(i + N);
   }
   vector<pair<int, int>> qs;
   for (int i = 0; i < Q; ++i) qs.emplace_back(G[i], i);
   sort(qs.begin(), qs.end());
   vector<int> ans(Q);
   auto go = [&](int start) {
      vector<int> dist(2 * N, -1);
      vector<int> q;
      dist[start] = 0;
      q.emplace_back(start);
      for (int i = 0; i < int(q.size()); ++i) {
         int v = q[i];
         for (int u : adj[v]) if (dist[u] == -1) {
            dist[u] = dist[v] + 1;
            q.emplace_back(u);
         }
      }
      vector<int> dists;
      for (int v : q) if (v < N) dists.emplace_back(dist[v]);
      int len = 0;
      vector<bool> visited(2 * N);
      int v = start;
      while (!visited[v]) {
         visited[v] = true;
         v = nxt[v];
         ++len;
      }
      if (v != start) len = -1;
      vector<int> cnts(2 * N);
      int ptr = 0;
      for (int i = 0; i < Q; ++i) {
         while (ptr < int(dists.size()) && dists[ptr] <= qs[i].first) {
            int cur = dists[ptr++];
            if (len != -1) cur %= len;
            ++cnts[cur];
         }
         int cur = qs[i].first;
         if (len != -1) cur %= len;
         if (cur < 2 * N) ans[qs[i].second] += cnts[cur];
      }
   };
   go(P);
   if (deg[P] > 1) go(P + N);
   for (int i = 0; i < Q; ++i) answer(ans[i]);
}

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