oj.uz

Submission #703030

# Submission time Handle Problem Language Result Execution time Memory
703030 2023-02-25T16:21:07 Z Josia Sailing Race (CEOI12_race) C++17
55 / 100
 3000 ms 16236 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++) {
            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 15956 KB Output is correct
2 Incorrect 7 ms 15972 KB Output isn't correct
3 Incorrect 8 ms 15972 KB Output isn't correct
4 Correct 9 ms 15980 KB Output is correct
5 Correct 9 ms 15956 KB Output is correct
6 Correct 15 ms 15980 KB Output is correct
7 Correct 13 ms 16084 KB Output is correct
8 Incorrect 22 ms 15972 KB Output isn't correct
9 Correct 15 ms 15980 KB Output is correct
10 Correct 19 ms 15984 KB Output is correct
11 Correct 20 ms 15984 KB Output is correct
12 Correct 302 ms 16004 KB Output is correct
13 Incorrect 814 ms 16008 KB Output isn't correct
14 Correct 292 ms 16040 KB Output is correct
15 Execution timed out 3055 ms 16120 KB Time limit exceeded
16 Execution timed out 3046 ms 16084 KB Time limit exceeded
17 Execution timed out 3050 ms 16236 KB Time limit exceeded
18 Correct 474 ms 16084 KB Output is correct
19 Execution timed out 3052 ms 16084 KB Time limit exceeded
20 Execution timed out 3031 ms 16084 KB Time limit exceeded