Submission #55232

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55232	2018-07-06T14:57:15 Z	paulica	Sailing Race (CEOI12_race)	C++14	25 / 100	3000 ms	4836 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 (t != -1) check(dpA(t, x, d) + maxB, s);
            //TRACE(s _ t _ x _ i);
        }

        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, 1 - d) + maxB, s);
        }

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

Subtask #1

25.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	376 KB	Output isn't correct
2	Incorrect	2 ms	612 KB	Output isn't correct
3	Correct	3 ms	816 KB	Output is correct
4	Correct	6 ms	816 KB	Output is correct
5	Incorrect	2 ms	892 KB	Output isn't correct
6	Correct	19 ms	1088 KB	Output is correct
7	Incorrect	3 ms	1088 KB	Output isn't correct
8	Correct	33 ms	1196 KB	Output is correct
9	Incorrect	3 ms	1452 KB	Output isn't correct
10	Incorrect	3 ms	1452 KB	Output isn't correct
11	Incorrect	3 ms	1452 KB	Output isn't correct
12	Incorrect	491 ms	2324 KB	Output isn't correct
13	Correct	1496 ms	3292 KB	Output is correct
14	Incorrect	8 ms	3936 KB	Output isn't correct
15	Execution timed out	3045 ms	4836 KB	Time limit exceeded
16	Execution timed out	3043 ms	4836 KB	Time limit exceeded
17	Execution timed out	3006 ms	4836 KB	Time limit exceeded
18	Incorrect	6 ms	4836 KB	Output isn't correct
19	Execution timed out	3035 ms	4836 KB	Time limit exceeded
20	Execution timed out	3047 ms	4836 KB	Time limit exceeded