oj.uz

답안 #552117

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
552117 2022-04-22T12:55:02 Z Alexandruabcde Sailing Race (CEOI12_race) C++14
85 / 100
 653 ms 5016 KB 
#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

# 결과 실행 시간 메모리 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