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

race

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

Subtask #1

55.0 / 100.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