답안 #55236

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55236 2018-07-06T15:34:21 Z paulica Sailing Race (CEOI12_race) C++14
5 / 100
3000 ms 4820 KB
#include <bits/stdc++.h>
using namespace std;

#define _ << " _ " <<
#define TRACE(x) cout << #x << " = " << x << endl

const int MaxN = 510;
int n, m;
int sol, start;

bool con[MaxN][MaxN];

int memoA[MaxN][MaxN][2], memoB[MaxN][MaxN][2];

int nxt(int i, int d) {
    if (d == 1) return (i + 1) % n;
    return (i - 1 + n) % n;
}

int dpA(int i, int j, int d) {
    int& dp = memoA[i][j][d];
    if (dp != -1) return dp;
    
    if (i == j) dp = 1;
    else if (con[i][j]) dp = 2;
    else dp = 0;

    for (int k = i; k != j; k = nxt(k, d))
        if (con[k][j] && dpA(i, k, d) > 0) dp = max(dp, dpA(i, k, d) + 1);

    return dp;
}

int dpB(int i, int j, int d) {
    int& dp = memoB[i][j][d];
    if (dp != -1) return dp;

    dp = (i != j);

    for (int k = i; k != j; k = nxt(k, d))
        if (con[i][k]) {
            dp = max(dp, dpB(k, j, d) + 1);
            dp = max(dp, dpB(k, i, 1 - d) + 1);
        }

    return dp;
}

void check(int cnt, int s) {
    if (cnt > sol) {
        sol = cnt;
        start = s;
    }
}

void solveS(int x, int s, int d) {
    int maxB = 0, t = -1;

    for (int i = nxt(s, d); i != x; i = nxt(i, d)) {
        if (con[x][i])
            maxB = max(maxB, dpB(i, s, 1 - d));

        if (con[s][i]) {
            t = i;
            check(dpA(t, x, d) + maxB, s);
        }
    }
}

void solveT(int x, int t, int d) {
    int maxB = 0, s = -1;
    
    for (int i = nxt(x, d); i != t; i = nxt(i, d))
        if (con[i][t]) {
            s = i;
            break;
        }

    if (s == -1) return;

    for (int i = nxt(s, d); i != t; i = nxt(i, d))
        if (con[x][i])
            maxB = max(maxB, dpB(i, t, d));

    check(dpA(t, x, d) + maxB, s);
}

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

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        int j;
        for (cin >> j; j != 0; cin >> j)
            con[i][j - 1] = true;

        for (int j = 0; j < n; j++)
            for (int d : {0, 1})
                memoA[i][j][d] = memoB[i][j][d] = -1;
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int d : {0, 1})
                if (con[i][j]) check(dpB(j, i, d) + 1, i)/*, TRACE(i _ j _ d _ dpB(i, j, d) + 1)*/;

    if (m == 1) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i != j) {
                    solveS(i, j, 0);
                    solveS(i, j, 1);
                    solveT(i, j, 0);
                    solveT(i, j, 1);
                }
    }

    cout << sol << "\n" << start + 1 << "\n";

    return 0;
}

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Incorrect 3 ms 488 KB Output isn't correct
3 Incorrect 3 ms 684 KB Output isn't correct
4 Incorrect 6 ms 812 KB Output isn't correct
5 Incorrect 4 ms 844 KB Output isn't correct
6 Correct 16 ms 1020 KB Output is correct
7 Incorrect 11 ms 1032 KB Output isn't correct
8 Incorrect 33 ms 1180 KB Output isn't correct
9 Incorrect 17 ms 1480 KB Output isn't correct
10 Incorrect 25 ms 1480 KB Output isn't correct
11 Incorrect 24 ms 1480 KB Output isn't correct
12 Incorrect 502 ms 2276 KB Output isn't correct
13 Incorrect 1513 ms 3276 KB Output isn't correct
14 Incorrect 786 ms 3916 KB Output isn't correct
15 Execution timed out 3066 ms 4812 KB Time limit exceeded
16 Execution timed out 3024 ms 4812 KB Time limit exceeded
17 Execution timed out 3051 ms 4820 KB Time limit exceeded
18 Incorrect 1289 ms 4820 KB Output isn't correct
19 Execution timed out 3080 ms 4820 KB Time limit exceeded
20 Execution timed out 3041 ms 4820 KB Time limit exceeded