제출 #1146542

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146542		mannshah1211	9월 (APIO24_september)	C++20	100 / 100	459 ms	34884 KiB

september

#include <bits/stdc++.h>
#include "september.h"

using namespace std;

#ifdef LOCAL
#include "deb.h"
#else
#define debug(...) 
#endif

int solve(int n, int m, vector<int> f, vector<vector<int>> s) {
  mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
  int ans = 0;
  vector<vector<int>> g(n);
  for (int i = 1; i < n; i++) {
    g[f[i]].push_back(i);
  }
  vector<set<int>> sts(m);
  vector<int> violate(m);
  vector<long long> hashes(m);
  vector<long long> weights(n);
  for (int i = 0; i < n; i++) {
    weights[i] = rng() % 10000000;
  }
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < m; j++) {
      for (int who : g[s[j][i]]) {
        if (sts[j].find(who) == sts[j].end()) {
          violate[j]++;
        }
      }
      if (sts[j].find(f[s[j][i]]) != sts[j].end()) {
        violate[j]--;
      }
      sts[j].insert(s[j][i]);
    }
    bool ok = true;
    for (int j = 0; j < m; j++) {
      if (violate[j] != 0) {
        ok = false;
      }
    }
    for (int j = 0; j < m; j++) {
      hashes[j] += (long long) (s[j][i] + 1) * weights[s[j][i]];
    }
    for (int j = 0; j < m; j++) {
      if (hashes[j] != hashes[0]) {
        ok = false;
      }
    }
    ans += ok;
  }
  return ans;
}

• 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: 16 / 16