Submission #329093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
329093	2020-11-19T02:01:41 Z	thecodingwizard	Sailing Race (CEOI12_race)	C++11	100 / 100	1059 ms	5100 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];
vector<int> radj[maxn];
bool connected[maxn][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];

// return true if i --> j --> k is going counterclockwise
bool ccw(int i, int j, int k) {
    if (k < i) k += n;
    if (j < i) j += n;
    return i < j && j < k;
}

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);
            connected[i][x] = 1;
        }
    }

    int best = -1, bestIdx = -1;

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

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

    if (k) {
        F0R(i, n) {
            path[i][i] = 1;

            FOR(add, 0, n) {
                int j = (i+add)%n;

                if (connected[j][i]) {
                    FOR(add2, 1, n) {
                        int nxt = (j+add2)%n;
                        if (ccw(i, j, nxt) && path[i][nxt] > 0) {
                            int val = max(dp(nxt, i, 0), dp(j, nxt, 1)) + path[i][nxt] - 1;
                            if (best < val) {
                                best = val;
                                bestIdx = j;
                            }
                        }
                    }
                }

                if (path[i][j] > 0) {
                    for (int k : adj[j]) {
                        if (j == i || ccw(i, j, k)) path[i][k] = max(path[i][k], path[i][j]+1);
                    }
                }
            }

            pathRev[i][i] = 1;
            FOR(sub, 0, n) {
                int j = (i-sub+n)%n;

                if (connected[j][i]) {
                    FOR(sub2, 1, n) {
                        int nxt = (j-sub2+n)%n;
                        if (ccw(i, nxt, j) && pathRev[i][nxt] > 0) {
                            int val = max(dp(nxt, j, 0), dp(i, nxt, 1)) + pathRev[i][nxt] - 1;
                            //cout << j << "-->" << i << "--> ... -->" << nxt << ": " << val << endl;
                            if (best < val) {
                                best = val;
                                bestIdx = j;
                            }
                        }
                    }
                }

                //cout << "pathRev[" << i << "][" << j << "]: " << pathRev[i][j] << endl;
                if (pathRev[i][j] > 0) {
                    for (int k : adj[j]) {
                        if (j == i || ccw(i, k, j)) pathRev[i][k] = max(pathRev[i][k], pathRev[i][j] + 1);
                    }
                }
            }
        }
    }

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

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	512 KB	Output is correct
3	Correct	1 ms	620 KB	Output is correct
4	Correct	1 ms	748 KB	Output is correct
5	Correct	1 ms	620 KB	Output is correct
6	Correct	4 ms	876 KB	Output is correct
7	Correct	6 ms	748 KB	Output is correct
8	Correct	4 ms	1004 KB	Output is correct
9	Correct	6 ms	748 KB	Output is correct
10	Correct	17 ms	876 KB	Output is correct
11	Correct	8 ms	876 KB	Output is correct
12	Correct	59 ms	2156 KB	Output is correct
13	Correct	106 ms	2940 KB	Output is correct
14	Correct	68 ms	2284 KB	Output is correct
15	Correct	675 ms	4844 KB	Output is correct
16	Correct	859 ms	4972 KB	Output is correct
17	Correct	684 ms	4808 KB	Output is correct
18	Correct	90 ms	2668 KB	Output is correct
19	Correct	1059 ms	5040 KB	Output is correct
20	Correct	1053 ms	5100 KB	Output is correct