oj.uz

답안 #702203

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
702203 2023-02-23T10:12:22 Z Josia Sailing Race (CEOI12_race) C++17
40 / 100
 458 ms 16468 KB 
#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

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