제출 #1095208

#제출 시각아이디문제언어결과실행 시간메모리
1095208RiverFlow9월 (APIO24_september)C++17
100 / 100
303 ms37320 KiB
#include <bits/stdc++.h> #define nl "\n" #define no "NO" #define yes "YES" #define fi first #define se second #define vec vector #define task "main" #define _mp make_pair #define ii pair<int, int> #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define evoid(val) return void(std::cout << val) #define FOR(i, a, b) for(int i = (a); i <= (b); ++i) #define FOD(i, b, a) for(int i = (b); i >= (a); --i) #define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin()) using namespace std; template<typename U, typename V> bool maxi(U &a, V b) { if (a < b) { a = b; return 1; } return 0; } template<typename U, typename V> bool mini(U &a, V b) { if (a > b or a == -1) { a = b; return 1; } return 0; } const int N = (int)1e5 + 9; const int mod = (int)1e9 + 7; int n, m; int mx[N], a[5][N], L[N], R[N]; vector<int> g[N]; void dfs(int u, int p) { mx[u] = R[u]; for(int v : g[u]) if (v != p) { dfs(v, u); mx[u] = max(mx[u], mx[v]); } } const int LG = 16; struct segment_tree { int n; const int INF = -(int)1e6; vector<int> t, lz; segment_tree () {}; segment_tree (int _n) { n = _n; t.resize(4 * n + 7); lz.resize(4 * n + 7); } void set_off(int id, int l, int r, int u, int v) { if (l > v or r < u) return ; if (l >= u and r <= v) { t[id] = INF; lz[id] = -1; return ; } if (lz[id] == -1) { t[id << 1] = t[id << 1 | 1] = INF; lz[id << 1] = lz[id << 1 | 1] = -1; lz[id] = 0; } int m = (l + r) >> 1; set_off(id << 1, l, m, u, v); set_off(id << 1 | 1, m + 1, r, u, v); t[id] = max(t[id << 1], t[id << 1 | 1]); } void set_off(int l, int r) { ++l, ++r; set_off(1, 1, n, l, r); } void update(int id, int l, int r, int p, int val) { if (l == r) return void(t[id] = val); if (lz[id] == -1) { t[id << 1] = t[id << 1 | 1] = INF; lz[id << 1] = lz[id << 1 | 1] = -1; lz[id] = 0; } int m = (l + r) >> 1; if (p <= m) update(id << 1, l, m, p, val); else update(id << 1 | 1, m + 1, r, p, val); t[id] = max(t[id << 1], t[id << 1 | 1]); } void set_on(int p, int val) { ++p; update(1, 1, n, p, val); } int get(int id, int l, int r, int u, int v) { if (l > v or r < u) return 0; if (l >= u and r <= v) return t[id]; if (lz[id] == -1) { t[id << 1] = t[id << 1 | 1] = INF; lz[id << 1] = lz[id << 1 | 1] = -1; lz[id] = 0; } int m = (l + r) >> 1; return max(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v)); } int get(int l, int r) { ++l, ++r; return get(1, 1, n, l, r); } }; int sp[N][LG + 1], lg[N]; int solve(int N, int M, vector<int> F, vector<vector<int>> S) { n = N, m = M; FOR(i, 0, n - 1) { g[i].clear(); L[i] = n; R[i] = mx[i] = 0; } for(int i = 0; i < m; ++i) { for(int j = 0; j < n - 1; ++j) a[i][j] = S[i][j]; } for(int i = 0; i < m; ++i) { for(int j = 0; j < n - 1; ++j) { maxi(R[a[i][j]], j); mini(L[a[i][j]], j); } } FOR(i, 1, n - 1) { g[F[i]].push_back(i); } dfs(0, -1); vector<int> d(n, 0); vector<int> dp(n, -1); FOR(i, 0, n - 1) { d[i] = n; for(int t = 0; t < m; ++t) { mini(d[i], L[a[t][i]]); } } auto get = [&](int l, int r) { int j = lg[r - l + 1]; return max(sp[l][j], sp[r - (1 << j) + 1][j]); }; for(int i = 0; i < n - 1; ++i) { sp[i][0] = mx[a[0][i]]; } for(int j = 1; (1 << j) < n; ++j) for(int i = 0; i + (1 << j) - 1 < n; ++i) { sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]); } FOR(i, 2, n) lg[i] = lg[i / 2] + 1; stack<int> st; segment_tree IT(n); for(int i = 0; i < n - 1; ++i) { int lb = 0, rb = i; int r = i + 1; while (lb <= rb) { int mid = (lb + rb) >> 1; if (get(mid, i) <= i) { r = mid; rb = mid - 1; } else lb = mid + 1; } while (st.size()) { int u = st.top(); if (d[u] > d[i]) { st.pop(); } else break ; } int b = (st.size() ? st.top() + 1 : 1); IT.set_off(b, i); if (b == d[i]) { if (b == 0 or dp[b - 1] != -1) IT.set_on(b, (b > 0 ? dp[b - 1] : 0)); } st.push(i); if (r <= i and get(0, i) <= i) { maxi(dp[i], IT.get(r, i) + 1); } } return dp[n - 2]; } #ifdef LOCAL void taskcase() { int N, M; assert(2 == scanf("%d%d", &N, &M)); std::vector<int> F(N); F[0] = -1; for (int i = 1; i < N; ++i) assert(1 == scanf("%d", &F[i])); std::vector<std::vector<int>> S(M, std::vector<int>(N - 1)); for (int i = 0; i < M; ++i) for (int j = 0; j < N - 1; ++j) assert(1 == scanf("%d", &S[i][j])); printf("%d\n", solve(N, M, F, S)); } int main() { ios::sync_with_stdio(0); cin.tie(0); freopen("main.inp", "r", stdin); freopen("main.out", "w", stdout); int T; assert(1 == scanf("%d", &T)); while(T--) taskcase(); return 0; } #endif
#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...