Submission #55266

#	Time	Username	Problem	Language	Result	Execution time	Memory
55266		paulica	Sailing Race (CEOI12_race)	C++14	100 / 100	2878 ms	4944 KiB

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