제출 #410412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410412		600Mihnea	Tropical Garden (IOI11_garden)	C++17	69 / 100	5053 ms	62780 KiB

garden

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

using namespace std;

const int K = 31;
const int N = 2 * 150000 + 7;
int n, m, city, from[N], to[N], y;
vector<int> g[N];

void add_edge(int a, int b) {
  from[y] = a;
  to[y] = b;
  g[a].push_back(y);
  y++;
}

int nxt[K][N];
bool contain[K][N];
int len_cycle[2], type_cycle[2];
int ff[N], tt[N];

void count_routes(int nn, int mm, int pp, int rr[][2], int qq, int gg[]) {
  n = nn;
  m = mm;
  city = pp;
  y = 0;
  for (int i = 0; i < n; i++) {
    g[i].clear();
  }
  for (int i = 0; i < m; i++) {
    add_edge(rr[i][0], rr[i][1]);
    add_edge(rr[i][1], rr[i][0]);
  }
  for (int i = 0; i < y; i++) {
    int b = to[i];
    if ((int) g[b].size() == 1) {
      nxt[0][i] = i ^ 1;
    } else {
      if ((i ^ 1) == g[b][0]) {
        nxt[0][i] = g[b][1];
      } else {
        nxt[0][i] = g[b][0];
      }
    }
    contain[0][i] = (b == city);
  }
  for (int bit = 1; bit < K; bit++) {
    for (int i = 0; i < y; i++) {
      nxt[bit][i] = nxt[bit - 1][nxt[bit - 1][i]];
      contain[bit][i] = contain[bit - 1][i] | contain[bit - 1][nxt[bit - 1][i]];
    }
  }
  len_cycle[0] = len_cycle[1] = -1;
  for (int ies = 0; ies < min(2, (int) g[city].size()); ies++) {
    int i = g[city][ies];
    if (!contain[K - 1][i]) {
      continue;
    }
    int sz = 0;
    for (int j = K - 1; j >= 0; j--) {
      if (!contain[j][i]) {
        sz += (1 << j);
        i = nxt[j][i];
      }
    }
    len_cycle[ies] = sz;
    {
      bool este = 0;
      int i = g[city][ies];
      for (int bit = 0; bit < K; bit++) {
        if (len_cycle[ies] & (1 << bit)) {
          este |= contain[bit][i];
          i = nxt[bit][i];
        }
      }
      ///type_cycle[ies][]
      assert(to[i] == city);
      if ((int) g[city].size() == 1) {
        type_cycle[ies] = 0;
      } else {
        if ((i ^ 1) == g[city][0]) {
          type_cycle[ies] = 1;
        } else {
          type_cycle[ies] = 0;
        }
      }
    ///  cout << i << " ===> " << to[i] << " and " << from[i] << " : " << city << "        " << len_cycle[ies] << "\n";
    ///  assert(from[i] == city);
    }
    len_cycle[ies]++;
  }
  vector<int> nodes;
  for (int a = 0; a < n; a++) {
    assert(!g[a].empty());
    int i = g[a][0];
    if (!contain[K - 1][i]) {
      ff[a] = -1;
      continue;
    }
    nodes.push_back(a);
    int sz = 0;
    for (int j = K - 1; j >= 0; j--) {
      if (!contain[j][i]) {
        sz += (1 << j);
        i = nxt[j][i];
      }
    }
    ff[a] = sz;
    {
      bool este = 0;
      int i = g[a][0];
      for (int bit = 0; bit < K; bit++) {
        if (ff[a] & (1 << bit)) {
          este |= contain[bit][i];
          i = nxt[bit][i];
        }
      }
      assert(to[i] == city);
      if ((int) g[from[i]].size() == 1) {
        tt[a] = 0;
      } else {
        if ((i ^ 1) == g[city][0]) {
          tt[a] = 1;
        } else {
          tt[a] = 0;
        }
      }
    }
    ff[a]++;
  }
  /**
  for (int i = 0; i < n; i++) {
    cout << ff[i] << " : " << tt[i] << "\n";
  }**/
  ///cout << len_cycle[0] << " and " << len_cycle[1] << "\n";
  for (int qind = 0; qind < qq; qind++) {
    int len_query = gg[qind], sol = 0;
    for (auto &a : nodes) {
      int cur = g[a][0];
      for (int bit = 0; (1 << bit) <= len_query; bit++) {
        if (len_query & (1 << bit)) {
          cur = nxt[bit][cur];
        }
      }
      int len = len_query;
      if (tt[a] == 0) {
        len -= ff[a];
        bool ok = (from[cur] == city);
        bool me = ok;
        if (len >= 0) {
          if (len_cycle[0] == -1) {
            me = 0;

          } else {
            if (type_cycle[0] == 0) {
              me = ((len % len_cycle[0]) == 0);
            } else {
              if (len_cycle[1] == -1) {
               // me = (len == len_cycle[0]);
                assert(0);
              } else {
                if (len_cycle[1] == 1) {
                  assert(0);
                } else {
               //   me = (len >= len_cycle[0] && (len - len_cycle[0]) % (len_cycle[0] + len_cycle[1]) == 0);
                }
              }
            }
          }
        }
       /// me = ok;
       /** if (me != ok) {
          cout << me << " and " << ok << "\n";
          cout << " = " << len_query << "\n";
          int i = g[a][0];
          for (int step = 1; step <= 100; step++) {
            cout << i << " ";
            i = nxt[0][i];
          }
          cout << "\n";
          i = g[a][0];
          for (int step = 1; step <= 100; step++) {
            cout << (from[i] == city) << " ";
            i = nxt[0][i];
          }
          cout << "\n";
          exit(0);
        }**/
        assert(me == ok);
      } else {
        if (a == city) {

          bool ok = (from[cur] == city);
          bool me;
          if (len_cycle[0] == -1) {
            me = 0;
          } else {
            if (type_cycle[0] == 0) {
              me = ((len % len_cycle[0]) == 0);
            } else {
              if (len_cycle[1] == -1) {
                me = (len == len_cycle[0]);
                assert(0);
              } else {
                if (len_cycle[1] == 1) {
                  assert(0);
                } else {
                  me = (len >= len_cycle[0] && (len - len_cycle[0]) % (len_cycle[0] + len_cycle[1]) == 0);
                }
              }
            }
          }
          ///cout << ok << " and " << me << " : " << len << " and " << len_cycle[0] << "\n";
          ///exit(0);
          assert(ok == me);
        }
      }
      if (from[cur] == city) {
        sol++;
        if (cur == city) {

        }
      }
    }
    answer(sol);
  }
}

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