Submission #702203

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
702203	2023-02-23T10:12:22 Z	Josia	Sailing Race (CEOI12_race)	C++17	40 / 100	458 ms	16468 KB

race

#include <bits/stdc++.h>

#define int int64_t

using namespace std;

vector<vector<bool>> graphRev;

int n;
bool type;


int DP[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++) {
                    DP[i][j][k][l] = -1;
                }
            }
        }
    }
}


int dp(int l, int r, bool pos, bool start) {
    if (DP[l][r][pos][start] != -1) return DP[l][r][pos][start];
    int res = 0;
    for (int v = (l+1)%n; v!=r; v=(v+1)%n) {
        if (!graphRev[pos?r:l][v]) continue;

        // if (pos==0) {
            res = max(dp(l, v, 1, 0)+1, res);
            res = max(dp(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 DP[l][r][pos][start] = res;
}


signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    init();

    cin >> n;
    cin >> type;

    graphRev.assign(n,vector<bool>(n, 0));

    for (int i = 0; i<n; i++) {
        int x;
        cin >> x;
        while (x!=0) {
            // graphRev[x-1][i]=1;
            graphRev[i][x-1]=1;
            cin >> x;
        }
    }
    // for (auto i: graphRev) {
    //     for (int j: i) cerr << j << " ";
    //     cerr << "\n";
    // }
    // cerr << "\n";

    if (type == 0) {
        int res = 0;
        int ind = -1;

        for (int i = 0; i<n; i++) {
            if (dp(i, i, 0, 1) > res) {
                res = dp(i, i, 0, 1);
                ind = i;
            }
            // cerr << "---------\n";
        }

        cout << res << "\n" << ind+1 << "\n";
        return 0;
    }

    assert(0);


    return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8020 KB	Output is correct
2	Runtime error	11 ms	16284 KB	Execution killed with signal 6
3	Runtime error	10 ms	16340 KB	Execution killed with signal 6
4	Runtime error	10 ms	16340 KB	Execution killed with signal 6
5	Correct	5 ms	8152 KB	Output is correct
6	Runtime error	11 ms	16336 KB	Execution killed with signal 6
7	Correct	7 ms	8148 KB	Output is correct
8	Runtime error	11 ms	16340 KB	Execution killed with signal 6
9	Correct	11 ms	8148 KB	Output is correct
10	Correct	13 ms	8148 KB	Output is correct
11	Correct	15 ms	8152 KB	Output is correct
12	Runtime error	12 ms	16400 KB	Execution killed with signal 6
13	Runtime error	11 ms	16388 KB	Execution killed with signal 6
14	Correct	297 ms	8168 KB	Output is correct
15	Runtime error	12 ms	16468 KB	Execution killed with signal 6
16	Runtime error	13 ms	16400 KB	Execution killed with signal 6
17	Runtime error	13 ms	16468 KB	Execution killed with signal 6
18	Correct	458 ms	8192 KB	Output is correct
19	Runtime error	13 ms	16404 KB	Execution killed with signal 6
20	Runtime error	13 ms	16416 KB	Execution killed with signal 6