Submission #55265

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55265	2018-07-06T18:58:15 Z	paulica	Sailing Race (CEOI12_race)	C++14	95 / 100	3000 ms	4984 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 dpA[MaxN][MaxN][2], dpB[MaxN][MaxN][2];

int nxt(int i, int d) {
    if (d == 1) return i == n - 1 ? 0 : i + 1;
    else return i == 0 ? n - 1 : i - 1;
}

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, s);
        }

        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, 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 d : {0, 1})
        for (int i = 0; i < n; i++) {
            dpA[i][i][d] = 1;

            for (int j = nxt(i, d); j != i; j = nxt(j, d)) {
                int& dp = dpA[i][j][d];

                if (con[i][j]) dp = 2;
                else dp = 0;

                for (int k = nxt(i, d); k != j; k = nxt(k, d))
                    if (con[k][j] && dpA[i][k][d] > 0) dp = max(dp, dpA[i][k][d] + 1);
            }
        }
    
    for (int len = 1; len < n; len++) 
        for (int d : {0, 1})
            for (int i = 0; i < n; i++) {
                int j;
                if (d == 1) j = i + len >= n ? i + len - n : i + len;
                else j = i - len < 0 ? i - len + n : i - len;

                int& dp = dpB[i][j][d];
                dp = 1;

                for (int k = nxt(i, d); 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);
                    }
            }

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

    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

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	620 KB	Output is correct
3	Correct	3 ms	800 KB	Output is correct
4	Correct	4 ms	800 KB	Output is correct
5	Correct	5 ms	852 KB	Output is correct
6	Correct	7 ms	1048 KB	Output is correct
7	Correct	7 ms	1060 KB	Output is correct
8	Correct	13 ms	1192 KB	Output is correct
9	Correct	18 ms	1320 KB	Output is correct
10	Correct	12 ms	1472 KB	Output is correct
11	Correct	26 ms	1472 KB	Output is correct
12	Correct	157 ms	2240 KB	Output is correct
13	Correct	432 ms	3152 KB	Output is correct
14	Correct	485 ms	4076 KB	Output is correct
15	Correct	2755 ms	4956 KB	Output is correct
16	Correct	2475 ms	4956 KB	Output is correct
17	Correct	2554 ms	4956 KB	Output is correct
18	Correct	876 ms	4976 KB	Output is correct
19	Execution timed out	3056 ms	4984 KB	Time limit exceeded
20	Correct	2733 ms	4984 KB	Output is correct