답안 #55232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55232 2018-07-06T14:57:15 Z paulica Sailing Race (CEOI12_race) C++14
25 / 100
3000 ms 4836 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 (t != -1) check(dpA(t, x, d) + maxB, s);
            //TRACE(s _ t _ x _ i);
        }

        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, 1 - d) + maxB, s);
        }

    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;
    }
    
    // m = 0    

    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 2 ms 376 KB Output isn't correct
2 Incorrect 2 ms 612 KB Output isn't correct
3 Correct 3 ms 816 KB Output is correct
4 Correct 6 ms 816 KB Output is correct
5 Incorrect 2 ms 892 KB Output isn't correct
6 Correct 19 ms 1088 KB Output is correct
7 Incorrect 3 ms 1088 KB Output isn't correct
8 Correct 33 ms 1196 KB Output is correct
9 Incorrect 3 ms 1452 KB Output isn't correct
10 Incorrect 3 ms 1452 KB Output isn't correct
11 Incorrect 3 ms 1452 KB Output isn't correct
12 Incorrect 491 ms 2324 KB Output isn't correct
13 Correct 1496 ms 3292 KB Output is correct
14 Incorrect 8 ms 3936 KB Output isn't correct
15 Execution timed out 3045 ms 4836 KB Time limit exceeded
16 Execution timed out 3043 ms 4836 KB Time limit exceeded
17 Execution timed out 3006 ms 4836 KB Time limit exceeded
18 Incorrect 6 ms 4836 KB Output isn't correct
19 Execution timed out 3035 ms 4836 KB Time limit exceeded
20 Execution timed out 3047 ms 4836 KB Time limit exceeded