Submission #1187459

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187459		equation_tracker	September (APIO24_september)	C++20	48 / 100	1012 ms	41004 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>> g {};
  set<ll> res_s{}, temp{};
  for (ll i = 0; i < N; i++) res_s.insert(i);
  for (ll i = 1; i < N; i++) g[F[i]].insert(i);
  loop (M) {
    map<ll, set<ll>> gt = g;
    set<ll> w{}, res{};
    for (ll j = 0; j < N - 1; j++) {
      ll node = S[i][j];
      w.insert(gt[node].begin(), gt[node].end());
      w.erase(node);
      gt[F[node]].erase(node);
      if (w.empty()) res.insert(j);
    }
    set_intersection(res.begin(), res.end(), res_s.begin(), res_s.end(), inserter(temp, temp.begin()));
    res_s = move(temp);
    temp.clear();
  }
  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: 0 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 0 / 11
• Subtask 7: 9 / 9
• Subtask 8: 0 / 11
• Subtask 9: 9 / 9
• Subtask 10: 0 / 16