답안 #55235

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55235 2018-07-06T15:28:30 Z paulica Sailing Race (CEOI12_race) C++14
5 / 100
3000 ms 4860 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, j)/*, 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 4 ms 668 KB Output isn't correct
4 Correct 7 ms 796 KB Output is correct
5 Incorrect 7 ms 872 KB Output isn't correct
6 Incorrect 17 ms 1004 KB Output isn't correct
7 Incorrect 10 ms 1184 KB Output isn't correct
8 Incorrect 35 ms 1232 KB Output isn't correct
9 Incorrect 19 ms 1388 KB Output isn't correct
10 Incorrect 24 ms 1388 KB Output isn't correct
11 Incorrect 25 ms 1388 KB Output isn't correct
12 Incorrect 519 ms 2412 KB Output isn't correct
13 Incorrect 1560 ms 3308 KB Output isn't correct
14 Incorrect 752 ms 4076 KB Output isn't correct
15 Execution timed out 3044 ms 4844 KB Time limit exceeded
16 Execution timed out 3028 ms 4860 KB Time limit exceeded
17 Execution timed out 3054 ms 4860 KB Time limit exceeded
18 Incorrect 1191 ms 4860 KB Output isn't correct
19 Execution timed out 3068 ms 4860 KB Time limit exceeded
20 Execution timed out 3054 ms 4860 KB Time limit exceeded