답안 #703031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
703031	2023-02-25T16:23:55 Z	Josia	Sailing Race (CEOI12_race)	C++17	55 / 100	3000 ms	16084 KB

race

#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

#	결과	실행 시간	메모리	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