Submission #55266

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55266	2018-07-06T19:05:39 Z	paulica	Sailing Race (CEOI12_race)	C++14	100 / 100	2878 ms	4944 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[2][MaxN][MaxN], dpB[2][MaxN][MaxN];

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[d][t][x] + maxB, s);
        }

        if (con[x][i])
            maxB = max(maxB, dpB[1 - d][i][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[d][i][t]);

    check(dpA[d][t][x] + 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[d][i][i] = 1;

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

                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[d][i][k] > 0) dp = max(dp, dpA[d][i][k] + 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[d][i][j];
                dp = 1;

                for (int k = nxt(i, d); k != j; k = nxt(k, d))
                    if (con[i][k]) {
                        dp = max(dp, dpB[d][k][j] + 1);
                        dp = max(dp, dpB[1 - d][k][i] + 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[d][j][i], 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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	504 KB	Output is correct
2	Correct	3 ms	616 KB	Output is correct
3	Correct	3 ms	692 KB	Output is correct
4	Correct	4 ms	992 KB	Output is correct
5	Correct	4 ms	992 KB	Output is correct
6	Correct	9 ms	1084 KB	Output is correct
7	Correct	8 ms	1084 KB	Output is correct
8	Correct	12 ms	1212 KB	Output is correct
9	Correct	15 ms	1340 KB	Output is correct
10	Correct	11 ms	1440 KB	Output is correct
11	Correct	20 ms	1440 KB	Output is correct
12	Correct	162 ms	2256 KB	Output is correct
13	Correct	447 ms	3304 KB	Output is correct
14	Correct	430 ms	3920 KB	Output is correct
15	Correct	2368 ms	4872 KB	Output is correct
16	Correct	2409 ms	4900 KB	Output is correct
17	Correct	2271 ms	4924 KB	Output is correct
18	Correct	838 ms	4924 KB	Output is correct
19	Correct	2878 ms	4924 KB	Output is correct
20	Correct	2877 ms	4944 KB	Output is correct