Submission #1183749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183749		vux2code	Sailing Race (CEOI12_race)	C++20	0 / 100	283 ms	8952 KiB

race

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

const ll maxN = 500 + 5;
const ll inf64 = (ll)1e18;

ll n, k;
ll f1[maxN][maxN][2]; // for two‐segment DP (one crossing)
ll f2[maxN][maxN][2]; // for simple path DP (no crossing)
vector<ll> adj[maxN];

// Next harbor in circular order
ll nx(ll x) {
    x++;
    if (x > n) x -= n;
    return x;
}

// is x strictly between st and en along the circle (counterclockwise)?
bool irg(ll st, ll en, ll x) {
    if (st == en || en == nx(st)) return false;
    if (st > en) return (x > st || x < en);
    return (st < x && x < en);
}

// inrange depending on direction flag
bool inrange(ll st, ll en, bool dir, ll x) {
    return dir ? irg(st, en, x) : irg(en, st, x);
}

// DP for one‐crossing case: you can switch to the other arc once
ll fin2d(ll st, ll en, bool dir) {
    ll &res = f1[st][en][dir];
    if (res != -1) return res;
    res = 0;
    for (ll i : adj[st]) {
        if (!inrange(st, en, dir, i)) continue;
        // either stay on this arc or switch arcs at i
        res = max(res,
                  1 + max(
                      fin2d(i, en, dir),
                      fin2d(i, st, !dir)
                  )
        );
    }
    return res;
}

// DP for classical no‐crossing: longest simple path from st to en along one arc
ll finz(ll st, ll en, bool dir) {
    ll &res = f2[st][en][dir];
    if (res != -1) return res;
    if (st == en) return res = 1;
    res = -inf64;
    for (ll i : adj[st]) {
        if (!inrange(st, en, dir, i)) continue;
        ll tmp = finz(i, en, dir);
        if (tmp > 0) res = max(res, tmp + 1);
    }
    return res;
}

// DP wrapper for one‐crossing: try a single cross after the first segment
ll fin1d(ll st, ll en, bool dir) {
    ll ans = 0;
    for (int mid = 1; mid <= n; mid++) {
        if (!inrange(st, en, dir, mid)) continue;
        ll prefix = finz(st, mid, dir);
        if (prefix <= 0) continue;
        for (ll nxt : adj[mid]) {
            if (inrange(st, en, dir, nxt)) continue;
            // cross at (mid -> nxt)
            ans = max(ans, prefix + fin2d(nxt, st, dir));
            ans = max(ans, prefix + fin2d(nxt, en, !dir));
        }
    }
    return ans;
}

void solve() {
    cin >> n >> k;
    // read graph
    for (int i = 1; i <= n; i++) {
        adj[i].clear();
        ll x;
        while (cin >> x && x > 0) {
            adj[i].push_back(x);
        }
    }
    // init DP tables
    memset(f1, -1, sizeof f1);
    memset(f2, -1, sizeof f2);

    ll bestLen = 0, bestStart = 1;
    // try every possible first stage s->t
    for (int s = 1; s <= n; s++) {
        for (ll t : adj[s]) {
            if (k == 0) {
                // classical: one segment s->t + simple path back
                for (int dir = 0; dir < 2; dir++) {
                    ll verts = finz(t, s, dir);
                    if (verts > 0) {
                        ll edges = 1 + (verts - 1);
                        if (edges > bestLen) {
                            bestLen = edges;
                            bestStart = s;
                        }
                    }
                }
            } else {
                // one crossing allowed
                for (int dir = 0; dir < 2; dir++) {
                    ll extra = fin1d(t, s, dir);
                    ll edges = 1 + extra;
                    if (edges > bestLen) {
                        bestLen = edges;
                        bestStart = s;
                    }
                }
            }
        }
    }

    cout << bestLen << " " << bestStart << '\n';
}

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

    solve();
    return 0;
}

• Subtask 1: 0 / 100