oj.uz

답안 #552118

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

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