답안 #55234

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55234 2018-07-06T14:59:52 Z paulica Sailing Race (CEOI12_race) C++14
25 / 100
3000 ms 9364 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;
    }
   assert(m == 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 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 4 ms 904 KB Output isn't correct
3 Correct 4 ms 980 KB Output is correct
4 Correct 6 ms 1024 KB Output is correct
5 Runtime error 4 ms 1572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Correct 17 ms 1616 KB Output is correct
7 Runtime error 4 ms 1928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 31 ms 2064 KB Output is correct
9 Runtime error 4 ms 2280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 5 ms 2428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 4 ms 2456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 475 ms 3356 KB Output isn't correct
13 Correct 1531 ms 4248 KB Output is correct
14 Runtime error 11 ms 7548 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Execution timed out 3035 ms 8532 KB Time limit exceeded
16 Execution timed out 3063 ms 8532 KB Time limit exceeded
17 Execution timed out 3047 ms 8532 KB Time limit exceeded
18 Runtime error 12 ms 9312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Execution timed out 3073 ms 9364 KB Time limit exceeded
20 Execution timed out 3040 ms 9364 KB Time limit exceeded