oj.uz

Submission #703031

# Submission time Handle Problem Language Result Execution time Memory
703031 2023-02-25T16:23:55 Z Josia Sailing Race (CEOI12_race) C++17
55 / 100
 3000 ms 16084 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++) {
    //         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 7 ms 15884 KB Output is correct
2 Incorrect 7 ms 15956 KB Output isn't correct
3 Incorrect 7 ms 15872 KB Output isn't correct
4 Correct 9 ms 15956 KB Output is correct
5 Correct 8 ms 15980 KB Output is correct
6 Correct 14 ms 15980 KB Output is correct
7 Correct 11 ms 15912 KB Output is correct
8 Incorrect 20 ms 15976 KB Output isn't correct
9 Correct 16 ms 15956 KB Output is correct
10 Correct 19 ms 15956 KB Output is correct
11 Correct 19 ms 15956 KB Output is correct
12 Correct 247 ms 15956 KB Output is correct
13 Incorrect 683 ms 16084 KB Output isn't correct
14 Correct 296 ms 15992 KB Output is correct
15 Execution timed out 3083 ms 15956 KB Time limit exceeded
16 Execution timed out 3049 ms 15956 KB Time limit exceeded
17 Execution timed out 3069 ms 15956 KB Time limit exceeded
18 Correct 486 ms 16016 KB Output is correct
19 Execution timed out 3079 ms 16028 KB Time limit exceeded
20 Execution timed out 3083 ms 15956 KB Time limit exceeded