Submission #993180

#TimeUsernameProblemLanguageResultExecution timeMemory
993180hackstarSeptember (APIO24_september)C++17
100 / 100
868 ms44976 KiB
#pragma GCC optimize("O2,unroll-loops") #include "september.h" #include <string> #include <cstdio> #include <array> #include <vector> #include <algorithm> struct max_segtree { std::vector<int> st; int n; max_segtree(int n) : st(n * 2), n(n) {} void pul(int i) { st[i] = std::max(st[i << 1], st[i << 1 | 1]); } int query(int l, int r) { int z = 0; for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l & 1) z = std::max(z, st[l++]); if (r & 1) z = std::max(st[--r], z); } return z; } void assign(int p, int k) { for (st[p += n] = k; p /= 2; ) pul(p); } }; const int NN = 100000; const int MM = 5; std::vector<int> g[NN]; int M, tin[NN], tout[NN], timer, pos[MM][NN]; using Lena = std::array<int, 5>; void add_(Lena &a, const Lena &b) { int i; for (i = 0; i < M; ++i) a[i] = std::max(a[i], b[i]); } Lena add(Lena a, const Lena &b) { add_(a, b); return a; } void dfs(int u) { tin[u] = timer++; for (auto v : g[u]) dfs(v); tout[u] = timer - 1; } struct lena_segtree { std::vector<Lena> st; int n; lena_segtree(int n) : st(n * 2), n(n) {} void pul(int i) { st[i] = add(st[i << 1], st[i << 1 | 1]); } Lena query(int l, int r) { Lena z {}; for (l += n, r += n + 1; l < r; l /= 2, r /= 2) { if (l & 1) add_(z, st[l++]); if (r & 1) add_(z, st[--r]); } return z; } void update(int p, int q, int k) { p += n; st[p][q] = std::max(st[p][q], k); for (; p /= 2; ) pul(p); } void update2(int p, const Lena &x) { add_(st[p += n], x); for (; p /= 2; ) pul(p); } }; int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) { int i, j; ::M = M; for (i = 0; i < N; ++i) g[i].clear(); timer = 0; if (M == 1) { auto S0 = S[0]; std::vector<int> pos(N); for (i = 0; i < N - 1; ++i) pos[S0[i]] = i; for (i = 1; i < N; ++i) g[F[i]].push_back(i); dfs(0); max_segtree ta(N), tb(N); for (i = 1; i < N; ++i) ta.assign(tin[i], pos[i]); for (i = N - 2; i >= 0; --i) { int u, last; u = S0[i]; last = ta.query(tin[u], tout[u]); last = std::max(last, tb.query(i, last)); tb.assign(i, last); } int K = 0; for (i = 0; i < N - 1;) { int until; until = tb.query(i, i); i = until + 1; ++K; } return K; } for (i = 0; i < M; ++i) for (j = 0; j < N - 1; ++j) pos[i][S[i][j]] = j; for (i = 1; i < N; ++i) g[F[i]].push_back(i); dfs(0); std::vector<lena_segtree> tb; std::vector<Lena> tc(N); lena_segtree ta(N); auto Put = [&](int u, Lena x) { add_(x, tc[u]); for (int j = 0; j < M; ++j) add_(x, tb[j].query(0, x[j])); for (int j = 0; j < M; ++j) tb[j].update2(pos[j][u], x); ta.update2(tin[u], x); add_(tc[u], x); }; for (i = 0; i < M; ++i) tb.emplace_back(N); for (i = 0; i < M; ++i) for (j = 1; j < N; ++j) ta.update(tin[j], i, pos[i][j]); int is_line_graph = 1; for (int i = 1; i < N; ++i) is_line_graph &= F[i] == i - 1; if (not is_line_graph) { int what = 3; if (N >= 2001) what = 1; for (i = 0; i < what; ++i) { for (j = 0; j < N - 1; ++j) { int u = S[i][j]; Put(u, ta.query(tin[u], tout[u])); } } } for (i = 1; i < N; ++i) Put(i, ta.query(tin[i], tout[i])); Lena at {}; int K = 0; while (1) { for (j = 0; j < M; ++j) if (at[j] >= N - 1) return K; for (j = 0; j < M; ++j) add_(at, tc[S[j][at[j]]]); for (j = 0; j < M; ++j) ++at[j]; ++K; } }
#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...