Submission #1184485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184485		vux2code	Sailing Race (CEOI12_race)	C++20	0 / 100	496 ms	5600 KiB

race

#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 500;
int N, K;
vector<int> adj[MAXN];
int f2_dp[MAXN][MAXN][2]; // classical DP: max edges from st to en, no crossing
char vis2[MAXN][MAXN][2];
int f1_dp[MAXN][MAXN][2]; // one-crossing DP: max edges from st to en, at most one crossing
char vis1[MAXN][MAXN][2];

// Check if x lies strictly between st and en along the circle in direction dir
inline bool inrange(int st, int en, int dir, int x) {
    if (x == st || x == en) return false;
    if (dir == 0) {
        int d_se = (en - st + N) % N;
        int d_sx = (x - st + N) % N;
        return (d_sx > 0 && d_sx < d_se);
    } else {
        int d_se = (st - en + N) % N;
        int d_sx = (st - x + N) % N;
        return (d_sx > 0 && d_sx < d_se);
    }
}

// Classical DP: no crossings allowed
int dfs2(int st, int en, int dir) {
    int &res = f2_dp[st][en][dir];
    if (vis2[st][en][dir]) return res;
    vis2[st][en][dir] = 1;
    if (st == en) {
        return res = 0;
    }
    int best = -1000000000;
    for (int nxt : adj[st]) {
        if (nxt == en || inrange(st, en, dir, nxt)) {
            int tmp = dfs2(nxt, en, dir);
            if (tmp >= 0) best = max(best, tmp + 1);
        }
    }
    return res = best;
}

// One-crossing DP: at most one crossing with chord st-en
int dfs1(int st, int en, int dir) {
    int &res = f1_dp[st][en][dir];
    if (vis1[st][en][dir]) return res;
    vis1[st][en][dir] = 1;
    // Case 0: no crossing at all
    int best = dfs2(st, en, dir);
    // Try transitions
    for (int nxt : adj[st]) {
        if (nxt == en || inrange(st, en, dir, nxt)) {
            // no crossing on this edge
            int tmp = dfs1(nxt, en, dir);
            if (tmp >= 0) best = max(best, tmp + 1);
        } else {
            // crossing occurs on this edge
            int tmp = dfs2(nxt, en, 1 - dir);
            if (tmp >= 0) best = max(best, tmp + 1);
        }
    }
    return res = best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        while (true) {
            int x; cin >> x;
            if (x == 0) break;
            adj[i].push_back(x - 1);
        }
    }

    // Initialize DP visited arrays
    memset(vis2, 0, sizeof(vis2));
    memset(vis1, 0, sizeof(vis1));

    int answer = 0;
    int startHarbor = 1;

    // Precompute all f2 and f1 states on demand
    for (int s = 0; s < N; s++) {
        for (int t : adj[s]) {
            for (int dir = 0; dir < 2; dir++) {
                int val;
                if (K == 0) {
                    val = dfs2(t, s, dir);
                } else {
                    val = dfs1(t, s, dir);
                }
                if (val >= 0) val += 1; // add the first stage s->t
                if (val > answer) {
                    answer = val;
                    startHarbor = s + 1;
                }
            }
        }
    }

    // Output
    cout << answer << '\n' << startHarbor << '\n';
    return 0;
}

• Subtask 1: 0 / 100