Submission #552117

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
552117	2022-04-22T12:55:02 Z	Alexandruabcde	Sailing Race (CEOI12_race)	C++14	85 / 100	653 ms	5016 KB

race

#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 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;
}

Subtask #1

85.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	2 ms	596 KB	Output is correct
5	Correct	1 ms	724 KB	Output is correct
6	Correct	3 ms	852 KB	Output is correct
7	Correct	3 ms	852 KB	Output is correct
8	Correct	4 ms	1024 KB	Output is correct
9	Correct	5 ms	1108 KB	Output is correct
10	Correct	13 ms	1260 KB	Output is correct
11	Correct	7 ms	1108 KB	Output is correct
12	Incorrect	41 ms	2068 KB	Output isn't correct
13	Correct	87 ms	2908 KB	Output is correct
14	Correct	71 ms	3764 KB	Output is correct
15	Correct	462 ms	4736 KB	Output is correct
16	Incorrect	570 ms	4968 KB	Output isn't correct
17	Correct	474 ms	4724 KB	Output is correct
18	Correct	104 ms	4604 KB	Output is correct
19	Incorrect	653 ms	4928 KB	Output isn't correct
20	Correct	648 ms	5016 KB	Output is correct