제출 #1187447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187447		equation_tracker	September (APIO24_september)	C++20	45 / 100	643 ms	16104 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 {};
  ll res = 0;
  for (ll i = 1; i < N; i++) g[F[i]].insert(i);
  if (M == 1) {
    set<ll> waiting{};
    for (auto node: S[0]) {
      waiting.insert(g[node].begin(), g[node].end());
      waiting.erase(node);
      g[F[node]].erase(node);
      if (waiting.empty()) res++;
    }
    return res;
  }
  return 0;
}
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: 0 / 5
• Subtask 6: 0 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16