Submission #410483

#	Time	Username	Problem	Language	Result	Execution time	Memory
410483		600Mihnea	Tropical Garden (IOI11_garden)	C++17	100 / 100	2979 ms	65084 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];

bool ok;

bool func0(int len) {
  if (len < 0) return 0;
  if (len == 0) return 1;
  if (len_cycle[0] == -1) return 0;
  if (type_cycle[0] == 0) return (len % len_cycle[0] == 0);
  if (len_cycle[1] == -1) assert(0);
  if (len < len_cycle[0]) return 0;
  if (type_cycle[1] == 1) return (len - len_cycle[0]) % len_cycle[1] == 0;
  if (type_cycle[1] == 0) {
    int r = len % (len_cycle[0] + len_cycle[1]);
    if (r == 0 || r == len_cycle[0]) {
      return 1;
    } else {
      return 0;
    }
  }
  assert(0);
}

bool func1(int len) {
  if (len < 0) return 0;
  if (len == 0) return 1;
  if (len_cycle[1] == -1) return 0;



  if (type_cycle[1] == 1) return (len % len_cycle[1] == 0);
//  return ok;


  if (len_cycle[0] == -1) assert(0);
  if (len < len_cycle[1]) return 0;
  if (type_cycle[0] == 0) return (len - len_cycle[1]) % len_cycle[0] == 0;
  if (type_cycle[0] == 1) {
    int r = len % (len_cycle[0] + len_cycle[1]);
    if (r == 0 || r == len_cycle[1]) {
      return 1;
    } else {
      return 0;
    }
  }
  assert(0);
}


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];
        }
      }
      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;
        }
      }
    }
    len_cycle[ies]++;
  }
  vector<int> nodes;
  for (int a = 0; a < n; a++) {
    int i = g[a][0];
    if (!contain[K - 1][i] || a == city) {
      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];
        }
      }
      if ((int) g[city].size() == 1) {
        tt[a] = 0;
      } else {
        if ((i ^ 1) == g[city][0]) {
          tt[a] = 1;
        } else {
          tt[a] = 0;
        }
      }
    }
    ff[a]++;
  }
  tt[city] = 0;
  ff[city] = 0;
  nodes.push_back(city);
  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 me = func0(len);
        ok = me;
        //assert(me == ok);
      } else {
        len -= ff[a];
        bool me = func1(len);
        ok = me;
        //assert(me == ok);
      }
      if (ok) {
        sol++;
      }
    }
    answer(sol);
  }
}

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