제출 #1198671

#제출 시각아이디문제언어결과실행 시간메모리
1198671sheercold9월 (APIO24_september)C++20
0 / 100
1 ms324 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; int solve(int n, int m, std::vector<int> p, std::vector<std::vector<int>> s) { mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); vector<vector<int>> tree(n); for (int i = 1; i < n; i++) { tree[p[i]].push_back(i); } vector<int> mx(n); for (int i = 0; i < m; i++) { for (int j = 0; j < n - 1; j++) { mx[s[i][j]] = max(mx[s[i][j]], j); } } auto dfs = [&](auto&& self, int v) { for (int nxt : tree[v]) { if (nxt == p[v]) { continue; } self(self, nxt); mx[v] = max(mx[v], mx[nxt]); } }; vector<int> R(n - 1); iota(R.begin(), R.end(), 0); for (int i = 0; i < m; i++) { for (int j = 0; j < n - 1; j++) { R[j] = max(R[j], mx[s[i][j]]); } } vector<int> v(n - 1, 1); for (int iter = 0; iter < 30; iter++) { vector<int> hash(n); for (int i = 0; i < n; i++) { hash[i] = rng(); } vector<int> pref(m); for (int i = 0; i < n - 1; i++) { for (int j = 0; j < m; j++) { pref[j] ^= hash[s[j][i]]; } int valid = 1; for (int j = 1; j < m; j++) { valid &= pref[j] == pref[j - 1]; } v[i] &= valid; } } int ans = 0; for (int i = 0, r = 0; i < n - 1; i++) { r = max(r, R[i]); if (r <= i && v[i]) { ++ans; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...