Submission #55235

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

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