Submission #703042

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
703042	2023-02-25T17:24:46 Z	Josia	Sailing Race (CEOI12_race)	C++17	55 / 100	3000 ms	8268 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) << " " << 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 = -1;
            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)));
            }

            if (best == -1) continue;

            tmp += best;

            // cerr << i << " " << j << " " << dp2((j+n-1)%n, i, 0) << " " << 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	4 ms	8148 KB	Output is correct
2	Incorrect	4 ms	8020 KB	Output isn't correct
3	Incorrect	4 ms	8148 KB	Output isn't correct
4	Correct	5 ms	8148 KB	Output is correct
5	Correct	5 ms	8148 KB	Output is correct
6	Correct	9 ms	8148 KB	Output is correct
7	Correct	7 ms	8148 KB	Output is correct
8	Incorrect	14 ms	8152 KB	Output isn't correct
9	Correct	11 ms	8156 KB	Output is correct
10	Correct	14 ms	8148 KB	Output is correct
11	Correct	14 ms	8148 KB	Output is correct
12	Correct	197 ms	8268 KB	Output is correct
13	Incorrect	516 ms	8152 KB	Output isn't correct
14	Correct	292 ms	8164 KB	Output is correct
15	Incorrect	2830 ms	8192 KB	Output isn't correct
16	Execution timed out	3058 ms	8192 KB	Time limit exceeded
17	Incorrect	2818 ms	8188 KB	Output isn't correct
18	Correct	462 ms	8184 KB	Output is correct
19	Execution timed out	3046 ms	8148 KB	Time limit exceeded
20	Execution timed out	3071 ms	8192 KB	Time limit exceeded