oj.uz

Submission #703033

# Submission time Handle Problem Language Result Execution time Memory
703033 2023-02-25T16:37:54 Z Josia Sailing Race (CEOI12_race) C++17
55 / 100
 3000 ms 16032 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][2];
int DP2[500][500][2][2];


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


int dp1(int l, int r, bool pos, bool start) {
    if (DP1[l][r][pos][start] != -1) return DP1[l][r][pos][start];
    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, 0)+1, res);
            res = max(dp1(v, r, 0, 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][start] = res;
}

int dp2(int l, int r, bool pos, bool start) {
    if (DP2[l][r][pos][start] != -1) return DP2[l][r][pos][start];
    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, 0)+1, res);
        }
        if (pos==1) {
            res = max(dp2(l, v, 1, 0)+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][start] = 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, 1) > res) {
            res = dp1(i, i, 0, 1);
            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++) {
            int tmp = 2;
            if (dp2((j+n-1)%n, i, 1, 1) == -2) continue;
            tmp += dp2((j+n-1)%n, i, 1, 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, 1), dp1(i, k, 1, 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 < 2 || ((i+n-j)%n)-n > -2) continue;
            int tmp = 2;
            if (dp2((j+n-1)%n, i, 0, 1) == -2) continue;
            tmp += dp2((j+n-1)%n, i, 0, 1);
            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, 1), dp1(k, j, 0, 1)));
            }

            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 9 ms 15956 KB Output is correct
2 Incorrect 7 ms 16004 KB Output isn't correct
3 Incorrect 8 ms 15956 KB Output isn't correct
4 Correct 9 ms 15848 KB Output is correct
5 Correct 8 ms 15956 KB Output is correct
6 Correct 15 ms 15964 KB Output is correct
7 Correct 11 ms 15956 KB Output is correct
8 Incorrect 22 ms 15956 KB Output isn't correct
9 Correct 15 ms 15952 KB Output is correct
10 Correct 18 ms 15896 KB Output is correct
11 Correct 19 ms 15972 KB Output is correct
12 Correct 296 ms 15984 KB Output is correct
13 Incorrect 801 ms 15980 KB Output isn't correct
14 Correct 310 ms 15988 KB Output is correct
15 Execution timed out 3081 ms 15960 KB Time limit exceeded
16 Execution timed out 3077 ms 15956 KB Time limit exceeded
17 Execution timed out 3062 ms 16012 KB Time limit exceeded
18 Correct 472 ms 16032 KB Output is correct
19 Execution timed out 3062 ms 15956 KB Time limit exceeded
20 Execution timed out 3055 ms 15956 KB Time limit exceeded