Submission #552118

#TimeUsernameProblemLanguageResultExecution timeMemory
552118AlexandruabcdeSailing Race (CEOI12_race)C++14
85 / 100
653 ms4852 KiB
#include <bits/stdc++.h> using namespace std; constexpr int NMAX = 502; int N, K; vector <int> G[NMAX]; bool Exist[NMAX][NMAX]; void Read () { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> K; for (int i = 1; i <= N; ++ i ) { int x; cin >> x; while (x != 0) { G[i].push_back(x); Exist[i][x] = 1; cin >> x; } } } bool Between (int val, int st, int dr) { if (st <= dr) return (st <= val && val <= dr); return (st <= val || val <= dr); } int Before (int val) { if (val > 1) return val-1; return N; } int After (int val) { if (val < N) return val + 1; return 1; } int dp[NMAX][NMAX][2]; int cons[NMAX][NMAX][2]; void Precompute () { for (int i = 1; i <= N; ++ i ) for (int j = 1; j <= N; ++ j ) for (int c = 0; c < 2; ++ c ) dp[i][j][c] = 0; for (int lg = 2; lg <= N; ++ lg ) { for (int i = 1; i <= N; ++ i ) { int j = i + lg - 1; if (j > N) j -= N; dp[i][j][0] = dp[i][j][1] = 0; ///Caz I: din i for (auto vec : G[i]) { if (!Between(vec, i, j)) continue; dp[i][j][0] = max(dp[i][j][0], 1 + max(dp[After(i)][vec][1], dp[vec][j][0])); } ///Caz II: din j for (auto vec : G[j]) { if (!Between(vec, i, j)) continue; dp[i][j][1] = max(dp[i][j][1], 1 + max(dp[i][vec][1], dp[vec][Before(j)][0])); } } } for (int lg = 2; lg <= N; ++ lg ) { for (int i = 1; i <= N; ++ i ) { int j = i + lg - 1; if (j > N) j -= N; cons[i][j][0] = cons[i][j][1] = 0; for (auto vec : G[i]) { if (!Between(vec, i, j)) continue; if (vec == j) cons[i][j][0] = max(cons[i][j][0], 1); else if (cons[vec][j][0] != 0) cons[i][j][0] = max(cons[i][j][0], 1 + cons[vec][j][0]); } for (auto vec : G[j]) { if (!Between(vec, i, j)) continue; if (vec == i) cons[i][j][1] = max(cons[i][j][1], 1); else if (cons[i][vec][1] != 0) cons[i][j][1] = max(cons[i][j][1], 1 + cons[i][vec][1]); } } } } void Solve_Case_0 () { int ans = 0, start = 1; for (int i = 1; i <= N; ++ i ) { for (auto vec : G[i]) { ///i -> vec int posib = 1 + max(dp[After(i)][vec][1], dp[vec][Before(i)][0]); if (posib > ans) { ans = posib; start = i; } } } cout << ans << '\n' << start << '\n'; } void Solve_Case_1 () { ///AB intersect CD int ans = 0, Start = 1; for (int i = 1; i <= N; ++ i ) { for (auto vec : G[i]) { ///i -> vec int posib = 1 + max(dp[After(i)][vec][1], dp[vec][Before(i)][0]); if (posib > ans) { ans = posib; Start = i; } } } for (int B = 1; B <= N; ++ B ) { ///B -> C clockwise for (int C = 1; C <= N; ++ C ) { if (B == C) continue; if (cons[B][C][0] == 0) continue; int best_A = -1; int A = After(C); while (A != B) { if (Exist[A][B]) { best_A = A; break; } A = After(A); } if (best_A == -1) continue; int D = After(best_A); while (D != B) { if (Exist[C][D]) { int posib = 2 + cons[B][C][0] + max(dp[After(best_A)][D][1], dp[D][Before(B)][0]); if (posib > ans) { ans = posib; Start = best_A; } } D = After(D); } } ///B->C counterclockwise for (int C = 1; C <= N; ++ C ) { if (B == C) continue; if (cons[C][B][1] == 0) continue; int best_A = -1; int A = Before(C); while (A != B) { if (Exist[A][B]) { best_A = A; break; } A = Before(A); } if (best_A == -1) continue; int D = Before(best_A); while (D != B) { if (Exist[C][D]) { int posib = 2 + cons[C][B][1] + max(dp[D][Before(best_A)][0], dp[Before(B)][D][1]); if (posib > ans) { ans = posib; Start = best_A; } } D = Before(D); } } } cout << ans << '\n' << Start << '\n'; } int main () { Read(); Precompute(); if (K == 0) Solve_Case_0 (); else Solve_Case_1 (); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...