제출 #1000792

#제출 시각아이디문제언어결과실행 시간메모리
1000792vuavisao9월 (APIO24_september)C++17
75 / 100
221 ms25296 KiB
#include "september.h" #include <vector> #include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 100'000 + 10; const int INF = 1'000'000'000; struct FenWick { int n_node = 0; int tree[N]; void resize(int n) { n_node = n; for (int i = 0; i <= n_node; ++ i) tree[i] = 0; } FenWick() {}; FenWick(int n) { this->resize(n); }; void Update(int idx, int val) { for ( ; idx <= n_node; idx += (idx & - idx)) tree[idx] += val; return; } int Query(int idx) { int res = 0; for ( ; idx > 0; idx -= (idx & - idx)) res += tree[idx]; return res; } int Sum_to(int l, int r) { if (l > r) return 0; return Query(r) - Query(l - 1); } int kth(int val) { int res = 0, s = 0; for (int mask = 30; mask >= 0; -- mask) { int nxt = res | (1 << mask); if (nxt < n_node && s + tree[nxt] < val) { res = nxt; s += tree[nxt]; } } ++ res; return res; } }; int n, m; int parent[N]; vector<int> g[N]; int perRem[10][N]; int need[10][N]; namespace Order { int indexing[N]; FenWick bit; void dfs(int u, int res[]) { int idx = indexing[u]; res[idx] = idx; for (const auto& v : g[u]) { dfs(v, res); res[idx] = max(res[idx], res[indexing[v]]); } } void solve(int perRem[], int res[]) { for (int i = 1; i < n; ++ i) { indexing[perRem[i]] = i; } indexing[1] = 0; dfs(1, res); } } namespace One { bool check() { return (m == 1); } struct FenWickMax { int n_node = 0; int tree[N]; void resize(int n) { n_node = n; for (int i = 0; i <= n_node; ++ i) tree[i] = -INF; } FenWickMax() {}; FenWickMax(int n) { this->resize(n); }; void Update(int idx, int val) { for ( ; idx > 0; idx -= (idx & - idx)) tree[idx] = max(tree[idx], val); return; } int Query(int idx) { int res = -INF; for ( ; idx <= n_node; idx += (idx & - idx)) res = max(res, tree[idx]); return res; } }; vector<int> open[N]; int dp[N]; FenWick bit; FenWickMax bitMax; int solve() { for (int i = 0; i <= n + 1; ++ i) { vector<int>().swap(open[i]); dp[i] = -INF; } for (int i = 1; i < n; ++ i) { open[need[1][i]].push_back(i); } dp[0] = 0; bit.resize(n); for (int i = 1; i < n; ++ i) bit.Update(i, 1); bitMax.resize(n); for (int i = 1; i < n; ++ i) { for (const auto& idx : open[i]) bit.Update(idx, -1); bitMax.Update(i, dp[i - 1]); int cnt = bit.Query(i); int last = bit.kth(cnt) + (cnt != 0); if (last <= i) { dp[i] = bitMax.Query(last) + 1; } } return dp[n - 1]; } } namespace Brute_force { bool check() { return (n <= 1'000); } unsigned seed = chrono::system_clock::now().time_since_epoch().count(); mt19937_64 rng(seed); ll Rand(ll a, ll b = 1ll * INF * INF) { return a + rng() % (b - a + 1); } bool can[1'010][1'010]; ll base[N]; ll Hash[10][N]; vector<int> open[N]; int exist[N]; int dp[N]; int solve() { srand(time(nullptr)); for (int i = 0; i <= n + 1; ++ i) { dp[i] = -INF; exist[i] = 0; vector<int>().swap(open[i]); } for (int i = 0; i <= n + 1; ++ i) { for (int j = 0; j <= n + 1; ++ j) { can[i][j] = false; } } for (int i = 1; i <= n; ++ i) base[i] = Rand(1); for (int i = 1; i <= m; ++ i) { for (int j = 1; j < n; ++ j) { Hash[i][j] = base[perRem[i][j]]; open[need[i][j]].push_back(j); } } for (int i = 1; i < n; ++ i) { ll xorHash[6]; memset(xorHash, 0, sizeof(xorHash)); for (int j = i; j < n; ++ j) { for (int k = 1; k <= m; ++ k) { xorHash[k] ^= Hash[k][j]; } if (*min_element(xorHash + 1, xorHash + 1 + m) == *max_element(xorHash + 1, xorHash + 1 + m)) { can[i][j] = true; } } } dp[0] = 0; for (int i = 1; i < n; ++ i) { for (const auto& idx : open[i]) ++ exist[idx]; for (int j = i; j >= 1; -- j) { if (exist[j] < m) break; if (can[j][i]) { // cout << j << ' ' << i << ' ' << dp[i] << ' ' << dp[j - 1] << '\n'; dp[i] = max(dp[i], dp[j - 1] + 1); } } } return dp[n - 1]; } } int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) { n = N; m = M; for (int i = 0; i <= n + 1; ++ i) g[i].clear(); for (int v = 2; v <= n; ++ v) { int u = F[v - 1] + 1; g[u].push_back(v); parent[v] = u; } for (int i = 0; i < m; ++ i) { for (int j = 0; j < n - 1; ++ j) { perRem[i + 1][j + 1] = S[i][j] + 1; } } for (int i = 1; i <= m; ++ i) { Order::solve(perRem[i], need[i]); } if (One::check()) { return One::solve(); } if (Brute_force::check()) { return Brute_force::solve(); } return 0; }
#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...