Submission #55252

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55252	2018-07-06T18:07:19 Z	paulica	Sailing Race (CEOI12_race)	C++14	75 / 100	3000 ms	4876 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[s][i]) {
            t = i;
            check(dpA(t, x, d) + maxB + 1, s);
//            TRACE(s _ t _ x _ i);
  //          TRACE(dpA(t, x, d) _ maxB);
         //   if (dpA(t, x, d) + maxB == 4) TRACE(s _ t _ x _ dpA(t, x, d) _ maxB);
      //      cout << endl;
        }

        if (con[x][i])
            maxB = max(maxB, dpB(i, s, 1 - d));
    }
}

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 + 1, s);
    //TRACE(x _ t _ s _ d);
    //TRACE(dpA(t, x, d) _ maxB);
    //cout << endl;
}

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

    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(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 - 1 << "\n" << start + 1 << "\n";

    return 0;
}

Subtask #1

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	3 ms	812 KB	Output is correct
4	Correct	7 ms	1124 KB	Output is correct
5	Correct	5 ms	1124 KB	Output is correct
6	Correct	20 ms	1192 KB	Output is correct
7	Correct	10 ms	1328 KB	Output is correct
8	Correct	34 ms	1328 KB	Output is correct
9	Correct	17 ms	1376 KB	Output is correct
10	Correct	24 ms	1376 KB	Output is correct
11	Correct	21 ms	1480 KB	Output is correct
12	Correct	489 ms	2324 KB	Output is correct
13	Correct	1453 ms	3292 KB	Output is correct
14	Correct	684 ms	4024 KB	Output is correct
15	Execution timed out	3056 ms	4836 KB	Time limit exceeded
16	Execution timed out	3029 ms	4836 KB	Time limit exceeded
17	Execution timed out	3005 ms	4836 KB	Time limit exceeded
18	Correct	1192 ms	4876 KB	Output is correct
19	Execution timed out	3032 ms	4876 KB	Time limit exceeded
20	Execution timed out	3025 ms	4876 KB	Time limit exceeded