Submission #328794

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
328794	2020-11-18T05:48:15 Z	thecodingwizard	Sailing Race (CEOI12_race)	C++11	40 / 100	984 ms	4844 KB

race

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010

#define maxn 500
int n, k; 
vector<int> adj[maxn];

int memo[maxn][maxn][2];
int dp(int x, int y, bool onY) {
    if (memo[x][y][onY] != -1) return memo[x][y][onY];
    int best = 1;

    for (int i : adj[onY ? y : x]) {
        bool legal = false;
        if (x < y) {
            if (x < i && i < y) {
                legal = true;
            }
        } else {
            if (i > x || i < y) {
                legal = true;
            }
        }
        if (!legal) continue;

        best = max(best, 1 + max(dp(x, i, 1), dp(i, y, 0)));
    }

    return memo[x][y][onY] = best;
}

// path[i][x] = longest path to x starting from i, going counterclockwise
int path[maxn][maxn];
// going clockwise
int pathRev[maxn][maxn];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> k;
    F0R(i, n) {
        int x;
        while (cin >> x && x != 0) {
            --x;
            adj[i].pb(x);
        }
    }

    int best = -1, bestIdx = -1;

    F0R(i, n) F0R(j, n) F0R(k, 2) memo[i][j][k] = -1;

    F0R(i, n) {
        path[i][i] = pathRev[i][i] = 1;
        F0R(add, n) {
            int cur = (i+add)%n;
            if (path[i][cur] == 0) continue;
            for (int nxt : adj[cur]) {
                if ((cur >= i && (nxt > cur || nxt < i)) || (cur <= i && (cur < nxt && nxt < i))) {
                        path[i][nxt] = max(path[i][nxt], path[i][cur]+1);
                }
            }
        }
        F0R(subtract, n) {
            int cur = (i-subtract+n)%n;
            if (pathRev[i][cur] == 0) continue;
            for (int nxt : adj[cur]) {
                if ((cur >= i && (i < nxt && nxt < cur)) || (cur <= i && (nxt > i || nxt < cur))) {
                    if (pathRev[i][cur] != 0)
                        pathRev[i][nxt] = max(pathRev[i][nxt], pathRev[i][cur]+1);
                }
            }
        }
    }
    /*
    F0R(i, n) {
        F0R(j, n) cout << "pathRev[" << i << "][" << j << "] = " << pathRev[i][j] << endl;
    }
    */

    F0R(i, n) {
        for (int j : adj[i]) {
            int val = max(dp(i, j, 1), dp(j, i, 0));

            if (k) {
                F0R(add, n) {
                    int cur = (i+add)%n;
                    int newVal = -1;
                    int newVal2 = -1;

                    if ((j > i && (cur > j || cur < i)) || (j < i && (i < cur && cur < j))) {
                        newVal = path[i][cur] + max(dp(j, cur, 1), dp(cur, i, 0)) - 2;
                    } else {
                        newVal2 = pathRev[i][cur] + max(dp(cur, j, 0), dp(i, cur, 1)) - 2;
                    }

                    val = max(val, max(newVal, newVal2));
                }
            }

            if (best < val) {
                best = val;
                bestIdx = i;
            }
        }
    }

    cout << best << endl;
    cout << bestIdx+1 << endl;

    return 0;
}

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Incorrect	1 ms	492 KB	Output isn't correct
3	Incorrect	1 ms	620 KB	Output isn't correct
4	Incorrect	2 ms	620 KB	Output isn't correct
5	Correct	2 ms	748 KB	Output is correct
6	Incorrect	3 ms	876 KB	Output isn't correct
7	Correct	6 ms	1004 KB	Output is correct
8	Incorrect	4 ms	1004 KB	Output isn't correct
9	Correct	8 ms	1132 KB	Output is correct
10	Correct	24 ms	1280 KB	Output is correct
11	Correct	11 ms	1132 KB	Output is correct
12	Incorrect	64 ms	2156 KB	Output isn't correct
13	Incorrect	122 ms	2796 KB	Output isn't correct
14	Correct	91 ms	3564 KB	Output is correct
15	Incorrect	585 ms	4460 KB	Output isn't correct
16	Incorrect	792 ms	4712 KB	Output isn't correct
17	Incorrect	605 ms	4588 KB	Output isn't correct
18	Correct	121 ms	4332 KB	Output is correct
19	Incorrect	896 ms	4844 KB	Output isn't correct
20	Incorrect	984 ms	4844 KB	Output isn't correct