Submission #552118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
552118	2022-04-22T12:56:16 Z	Alexandruabcde	Sailing Race (CEOI12_race)	C++14	85 / 100	653 ms	4852 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 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;
}

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	468 KB	Output is correct
4	Correct	1 ms	596 KB	Output is correct
5	Correct	2 ms	724 KB	Output is correct
6	Correct	3 ms	852 KB	Output is correct
7	Correct	4 ms	852 KB	Output is correct
8	Correct	4 ms	1028 KB	Output is correct
9	Correct	5 ms	1108 KB	Output is correct
10	Correct	13 ms	1236 KB	Output is correct
11	Correct	6 ms	1108 KB	Output is correct
12	Incorrect	42 ms	2040 KB	Output isn't correct
13	Correct	94 ms	2880 KB	Output is correct
14	Correct	97 ms	3724 KB	Output is correct
15	Correct	478 ms	4652 KB	Output is correct
16	Incorrect	572 ms	4748 KB	Output isn't correct
17	Correct	452 ms	4652 KB	Output is correct
18	Correct	124 ms	4568 KB	Output is correct
19	Incorrect	653 ms	4852 KB	Output isn't correct
20	Correct	650 ms	4768 KB	Output is correct