Submission #55237

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55237	2018-07-06T16:08:09 Z	paulica	Sailing Race (CEOI12_race)	C++14	65 / 100	3000 ms	4900 KB

race

#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), i)/*, TRACE(i _ j _ d _ dpB(j, i, d))*/;

    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;
}

Subtask #1

65.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Incorrect	3 ms	616 KB	Output isn't correct
3	Correct	4 ms	800 KB	Output is correct
4	Correct	6 ms	800 KB	Output is correct
5	Correct	4 ms	872 KB	Output is correct
6	Correct	16 ms	1040 KB	Output is correct
7	Correct	11 ms	1056 KB	Output is correct
8	Correct	31 ms	1192 KB	Output is correct
9	Correct	19 ms	1344 KB	Output is correct
10	Correct	28 ms	1344 KB	Output is correct
11	Correct	24 ms	1344 KB	Output is correct
12	Incorrect	496 ms	2384 KB	Output isn't correct
13	Correct	1459 ms	3196 KB	Output is correct
14	Correct	702 ms	4056 KB	Output is correct
15	Execution timed out	3044 ms	4856 KB	Time limit exceeded
16	Execution timed out	3012 ms	4864 KB	Time limit exceeded
17	Execution timed out	3039 ms	4864 KB	Time limit exceeded
18	Correct	1165 ms	4900 KB	Output is correct
19	Execution timed out	3049 ms	4900 KB	Time limit exceeded
20	Execution timed out	3044 ms	4900 KB	Time limit exceeded