oj.uz

Submission #703037

# Submission time Handle Problem Language Result Execution time Memory
703037 2023-02-25T17:00:06 Z Josia Sailing Race (CEOI12_race) C++17
55 / 100
 3000 ms 18160 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 < 1 || ((i+n-j)%n)-n > -1) 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 6 ms 15956 KB Output is correct
2 Incorrect 11 ms 15876 KB Output isn't correct
3 Incorrect 10 ms 15936 KB Output isn't correct
4 Correct 32 ms 16104 KB Output is correct
5 Correct 8 ms 15956 KB Output is correct
6 Correct 65 ms 16004 KB Output is correct
7 Correct 12 ms 15980 KB Output is correct
8 Incorrect 109 ms 16116 KB Output isn't correct
9 Correct 14 ms 15876 KB Output is correct
10 Correct 17 ms 15956 KB Output is correct
11 Correct 19 ms 15980 KB Output is correct
12 Correct 970 ms 16828 KB Output is correct
13 Incorrect 2189 ms 18160 KB Output isn't correct
14 Correct 292 ms 15956 KB Output is correct
15 Execution timed out 3072 ms 17468 KB Time limit exceeded
16 Execution timed out 3050 ms 17436 KB Time limit exceeded
17 Execution timed out 3053 ms 17480 KB Time limit exceeded
18 Correct 480 ms 16012 KB Output is correct
19 Execution timed out 3053 ms 17416 KB Time limit exceeded
20 Execution timed out 3047 ms 17284 KB Time limit exceeded