Submission #494068

#	Time	Username	Problem	Language	Result	Execution time	Memory
494068		ntabc05101	Tropical Garden (IOI11_garden)	C++14	100 / 100	117 ms	41216 KiB

garden

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

#define taskname ""

/*void answer(int res) {
  cout << res << "\n";
}*/

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  vector<int> nxt(N << 1, -1);
  for (int i = 0; i < M; i++) {
    bool f[] = {!(~nxt[R[i][0] << 1]), !(~nxt[R[i][1] << 1])};
    for (bool e: {0, 1}) {
      int &u = R[i][e], &v = R[i][e ^ 1];
      if (!(~nxt[u << 1])) {
        nxt[u << 1] = v << 1 | f[e ^ 1];
      }
      else {
        if (!(~nxt[u << 1 | 1])) {
          nxt[u << 1 | 1] = v << 1 | f[e ^ 1];
        }
      }
    }
  }

  for (int i = 0; i < N; i++) {
    if (!(~nxt[i << 1])) {
      continue;
    }
    if (~nxt[i << 1 | 1]) {
      continue;
    }
    nxt[i << 1 | 1] = nxt[i << 1] & ~1;
    if ((nxt[nxt[i << 1 | 1]] >> 1) == i) {
      nxt[i << 1 | 1] |= 1;
    }
  }
  //return ;

  vector<int> adj[N << 1];
  for (int i = 0; i < (N << 1); i++) {
    if (~nxt[i]) {
      adj[nxt[i]].push_back(i);
    }
  }

  auto bfs = [&](int s) -> vector<int> {
    vector<int> dst(N << 1, -1);
    queue<int> q; q.push(s);
    dst[s] = 0;
    while (!q.empty()) {
      auto u = q.front(); q.pop();
      for (auto &to: adj[u]) {
        if (!(~dst[to])) {
          dst[to] = dst[u] + 1;
          q.push(to);
        }
      }
    }
    return dst;
  };

  vector<int> dst[2];
  const int inf = (N << 1) + 10;
  int cyc_len[] = {inf, inf};
  for (bool e: {0, 1}) {
    int u = P << 1 | e;
    dst[e] = bfs(u);
    if (!(~nxt[u])) {
      continue;
    }
    if (!(~dst[e][nxt[u]])) {
      continue;
    }

    cyc_len[e] = dst[e][nxt[u]] - dst[e][u] + 1;
  }
  //return ;

  vector< vector<int> > gr[2];
  for (bool e: {0, 1}) {
    gr[e].resize(N << 1);
    for (int i = 0; i < (N << 1); i += 2) {
      auto &dst_ = dst[e][i];
      if (~dst_) {
        gr[e][dst_ % cyc_len[e]].push_back(dst_);
      }
    }
    for (auto &l: gr[e]) {
      sort(l.begin(), l.end());
    }
  }
  //return ;

  for (int i = 0; i < Q; i++) {
    int res = 0;
    for (bool e: {0, 1}) {
      if (cyc_len[e] >= inf) {
        if (G[i] < inf) {
          res += gr[e][G[i]].size();
        }
      }
      else {
        auto &L = gr[e][G[i] % cyc_len[e]];
        res += upper_bound(L.begin(), L.end(), G[i]) - L.begin();
      }
    }
    answer(res);
  }
}

/*int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  else {
    if (fopen(taskname".in", "r")) {
      freopen(taskname".in", "r", stdin);
      freopen(taskname".out", "w", stdout);
    }
  }

  cin.tie(0)->sync_with_stdio(0);

  int N, M, P; cin >> N >> M >> P;
  int R[M][2];
  for (int i = 0; i < M; i++) {
    cin >> R[i][0] >> R[i][1];
  }
  int Q; cin >> Q;
  int G[Q];
  for (int i = 0; i < Q; i++) {
    cin >> G[i];
  }

  //return 0;
  count_routes(N, M, P, R, Q, G);

  return 0;
}*/

/*
6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
 */

/*
5 5 2
1 0
1 2
3 2
1 3
4 2
2
3 1
 */

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