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

# 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