Submission #703041

# Submission time Handle Problem Language Result Execution time Memory
703041 2023-02-25T17:20:26 Z Josia Sailing Race (CEOI12_race) C++17
55 / 100
3000 ms 8276 KB
#include <bits/stdc++.h>

#define int int64_t

using namespace std;

vector<vector<bool>> graph;
// vector<vector<bool>> graphRev;

int n;
bool type;


int DP1[500][500][2];
int DP2[500][500][2];


void init() {
    for (int i=0; i<500; i++) {
        for (int j = 0; j<500; j++) {
            for (int k = 0; k<2; k++) {
                DP1[i][j][k] = -1;
                DP2[i][j][k] = -1;
            }
        }
    }
}


int dp1(int l, int r, bool pos) {
    if (DP1[l][r][pos] != -1) return DP1[l][r][pos];
    int res = 0;
    for (int v = (l+1)%n; v!=r; v=(v+1)%n) {
        if (!graph[pos?r:l][v]) continue;

        // if (pos==0) {
            res = max(dp1(l, v, 1)+1, res);
            res = max(dp1(v, r, 0)+1, res);
        // }
        // if (pos==1) {
        //     res = max(dp(l, v, 1, 0)+1, res);
        //     res = max(dp(v, r, 0, 0)+1, res);
        // }
    }
    // cerr << l << " " << r << " " << res << "\n";
    return DP1[l][r][pos] = res;
}

int dp2(int l, int r, bool pos) {
    if (DP2[l][r][pos] != -1) return DP2[l][r][pos];
    int res = -2;
    if ((l+1)%n==r) res = 0;
    for (int v = (l+1)%n; v!=r; v=(v+1)%n) {
        if (!graph[pos?r:l][v]) continue;

        if (pos==0) {
            // res = max(dp2(l, v, 1, 0)+1, res);
            res = max(dp2(v, r, 0)+1, res);
        }
        if (pos==1) {
            res = max(dp2(l, v, 1)+1, res);
            // res = max(dp(v, r, 0, 0)+1, res);
        }
    }
    // cerr << l << " " << r << " " << res << "\n";
    if (res == -1) res = -2;
    return DP2[l][r][pos] = res;
}


signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    init();

    cin >> n;
    cin >> type;

    graph.assign(n,vector<bool>(n, 0));

    for (int i = 0; i<n; i++) {
        int x;
        cin >> x;
        while (x!=0) {
            graph[i][x-1]=1;
            // graphRev[x-1][i]=1;
            cin >> x;
        }
    }


    int res = 0;
    int ind = -1;

    for (int i = 0; i<n; i++) {
        if (dp1(i, i, 0) > res) {
            res = dp1(i, i, 0);
            ind = i;
        }
    }

    if (type == 0) {
        cout << res << "\n" << ind+1 << "\n";
        return 0;
    }



    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            if ((i+n-j)%n < 1 || ((i+n-j)%n)-n > -1) continue;
            int tmp = 2;
            if (dp2((j+n-1)%n, i, 1) == -2) continue;
            tmp += dp2((j+n-1)%n, i, 1);
            int posFirst = -1;
            for (int k = i; k != j; k=(k+1)%n) {
                if (graph[k][i]) posFirst = k;
                // cerr << k << " " << i << "\n";
            }
            if (posFirst == -1) continue;

            int best = 0;
            for (int k = (i+1)%n; k != posFirst; k=(k+1)%n) {
                if (!graph[j][k]) continue;
                best = max(best, max(dp1(k, posFirst, 0), dp1(i, k, 1)));
            }

            tmp += best;

            // cerr << i << " " << j << " " << dp2((j+n-1)%n, i, 1, 1) << " " << tmp << "\n";

            if (tmp > res) {
                ind = posFirst;
                res = tmp;
            }
        }
    }

    // cerr << "-------\n";




    // for (int i = 0; i<n; i++) {
    //     for (int j = 0; j<n; j++) {
    //         dp2(i, j, 0, 0);
    //         dp2(i, j, 1, 0);
    //         dp2(i, j, 0, 1);
    //         dp2(i, j, 1, 1);
    //     }
    // }


    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            if ((i+n-j)%n < 1 || ((i+n-j)%n)-n > -1) continue;
            int tmp = 2;
            if (dp2((j+n-1)%n, i, 0) == -2) continue;
            tmp += dp2((j+n-1)%n, i, 0);
            int posFirst = -1;
            for (int k = j; k != i; k=(k+n-1)%n) {
                if (graph[k][j]) posFirst = k;
                // cerr << k << " " << i << "\n";
            }
            if (posFirst == -1) continue;

            int best = 0;
            for (int k = (j+n-1)%n; k != posFirst; k=(k+n-1)%n) {
                if (!graph[j][k]) continue;
                best = max(best, max(dp1(posFirst, k, 1), dp1(k, j, 0)));
            }

            tmp += best;

            // cerr << i << " " << j << " " << dp2((j+n-1)%n, i, 0, 1) << " " << tmp << "\n";

            if (tmp > res) {
                ind = posFirst;
                res = tmp;
            }
        }
    }






    cout << res << "\n" << ind+1 << "\n";


    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 8020 KB Output is correct
2 Incorrect 4 ms 8168 KB Output isn't correct
3 Incorrect 5 ms 8148 KB Output isn't correct
4 Correct 6 ms 8144 KB Output is correct
5 Correct 5 ms 8148 KB Output is correct
6 Correct 9 ms 8148 KB Output is correct
7 Correct 8 ms 8148 KB Output is correct
8 Incorrect 13 ms 8156 KB Output isn't correct
9 Correct 11 ms 8156 KB Output is correct
10 Correct 14 ms 8128 KB Output is correct
11 Correct 14 ms 8148 KB Output is correct
12 Correct 194 ms 8068 KB Output is correct
13 Incorrect 515 ms 8148 KB Output isn't correct
14 Correct 278 ms 8148 KB Output is correct
15 Incorrect 2779 ms 8188 KB Output isn't correct
16 Execution timed out 3054 ms 8276 KB Time limit exceeded
17 Incorrect 2783 ms 8188 KB Output isn't correct
18 Correct 452 ms 8184 KB Output is correct
19 Execution timed out 3071 ms 8148 KB Time limit exceeded
20 Execution timed out 3069 ms 8208 KB Time limit exceeded