제출 #1095194

#제출 시각아이디문제언어결과실행 시간메모리
1095194RiverFlow9월 (APIO24_september)C++17
55 / 100
1091 ms19512 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]); } } 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> dp(n + 1, -1); for(int i = 0; i < n - 1; ++i) { int r = 0; int e = n, b = 0; for(int j = i; j >= 0; --j) { r = max(r, mx[a[0][j]]); for(int t = 0; t < m; ++t) { mini(e, L[a[t][j]]); maxi(b, R[a[t][j]]); } if (r > i) break ; if (j <= e and b <= i and r <= i) { if (j == 0 or dp[j - 1] != -1) { maxi(dp[i], (j > 0 ? dp[j - 1] : 0) + 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...