Submission #55236

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55236	2018-07-06T15:34:21 Z	paulica	Sailing Race (CEOI12_race)	C++14	5 / 100	3000 ms	4820 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) + 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;
}

Subtask #1

5.0 / 100.0

#	Verdict	Execution time	Memory	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