Submission #1187686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187686		equation_tracker	September (APIO24_september)	C++17	84 / 100	1040 ms	39576 KiB

september

#pragma GCC optimize("Ofast", "O3")
#include "september.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#include <iostream>
#include <chrono>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
#define loop(x) for (ll i = 0; i < x; i++)
struct custom_hash {
  static uint64_t splitmix64(uint64_t x);
  size_t operator()(uint64_t x) const;
};
template <typename _Tp, typename Cm_fn=std::less<_Tp>>
using ordered_set = __gnu_pbds::tree<
  _Tp, __gnu_pbds::null_type, Cm_fn, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update
>;
template <typename _Tp>
class Fenwick_Tree {
private:
  std::vector<_Tp> Tree;
public:
  void init() {
    for (long long i = 1; i <= this->Tree.size(); i++) {
      long long parent = i + (i & -i);
      if (parent <= this->Tree.size()) {
        this->Tree[parent - 1] += this->Tree[i - 1];
      }
    }
  }
  _Tp sum(long long l, long long r) {
    long long sum = 0;
    while (r > 0) {
      sum += this->Tree[r - 1];
      r -= (r & -r);
    }
    l--;
    while (l > 0) {
      sum -= this->Tree[l - 1];
      l -= (l & -l);
    }
    return sum;
  }
  void update(long long index, long long difference) {
    while (index <= this->Tree.size()) {
      this->Tree[index - 1] += difference;
      index += (index & -index);
    }
  }
  Fenwick_Tree(const std::vector<_Tp> &array) {
    this->Tree = array;
    this->init();
  }
};
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
  map<ll, set<ll>> gm {};
  for (ll i = 1; i < N; i++) gm[F[i]].insert(i);
  set<ll> res_s{}, t{};
  loop(M) {
    set<ll> w{}, res{}; vector<bool> visited(N, false);
    map<ll, set<ll>> g = gm;
    for (ll j = 0; j < N - 1; j++) {
      for (auto &v: S) {
        w.insert(g[v[j]].begin(), g[v[j]].end());
        if (!visited[v[j]]) w.insert(v[j]);
      }
      g[F[S[i][j]]].erase(S[i][j]);
      w.erase(S[i][j]); visited[S[i][j]] = 1;
      if (w.empty()) res.insert(j);
    }
    if (res_s.empty()) res_s = res;
    else {
      t = res_s;
      for (auto x: t) if (!res.count(x)) res_s.erase(x);
    }
  }
  return res_s.size();
}
uint64_t custom_hash::splitmix64(uint64_t x) {
  x += 0x9e3779b97f4a7c15;
  x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  return x ^ (x >> 31);
}
size_t custom_hash::operator()(uint64_t x) const {
  static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  return splitmix64(x + FIXED_RANDOM);
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 0 / 16