제출 #1174960

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174960		vincentbucourt1	Sailing Race (CEOI12_race)	C++20	95 / 100	1379 ms	5700 KiB

race

#include <bits/stdc++.h>
using namespace std;
void fastIO(){ios_base::sync_with_stdio(false),cin.tie(0);}
#define int long long

const int MAXN = 520;

int N, type;
vector<int> adj[MAXN], invAdj[MAXN];
int dp[MAXN][MAXN][2];
int longest[MAXN];
bool canStart[MAXN];

int dist (int n1, int n2, int d) {
    return ((n2 - n1) / d + N*N) % N;
}
bool between (int n1, int n2, int n3, int d) {
    return (dist(n1, n2, d) + dist(n2, n3, d) == dist(n1, n3, d));
}

signed main() {
    fastIO();
    cin >> N >> type;
    for (int i = 0; i < N; i++) {
        int on;
        cin >> on;
        while (on != 0) {
            if (i != on-1) {
                adj[i].push_back(on-1);
                invAdj[on-1].push_back(i);
            }
            cin >> on;
        }
    }
    for (int len = 1; len < N; len++) {
        for (int node = 0; node < N; node++) {
            for (int mid : adj[node]) {
                int other = (node + len) % N;
                if (between(node, mid, other, 1)) {
                    dp[node][other][1] = max({dp[node][other][1], dp[mid][(node+1)%N][0] + 1, dp[mid][other][1] + 1});
                }
                other = (node - len + N) % N;
                if (between(node, mid, other, -1)) {
                    dp[node][other][0] = max({dp[node][other][0], dp[mid][(node-1+N)%N][1] + 1, dp[mid][other][0] + 1});
                }
            }
        }
    }
    int ans = 0, iAns = 0;
    for (int i = 0; i < N; i++) {
        if (ans < dp[i][(i+1)%N][0]) {
            ans = dp[i][(i+1)%N][0];
            iAns = i;
        }
    }
    if (type == 0) {
        cout << ans << "\n" << iAns+1 << "\n";
        return 0;
    }
    for (int second = 0; second < N; second++) {
        fill(canStart, canStart+N, false);
        bool canCont = false;
        for (int f : invAdj[second]) {
            canStart[f] = true;
            canCont = true;
        }
        if (!canCont) continue;
        // cerr << second << ":  ";
        // for (int i = 0; i < N; i++) cerr << canStart[i] << " ";
        // cerr << "\n";
        for (int d : {-1, 1}) {
            fill(longest, longest+N, 0);
            int dDp = (d == -1 ? 0 : 1);
            int first = second, lenFirst = 0;
            longest[second] = 1;
            for (int offset = 0; offset < N; offset++) {
                int node = (first + d*offset + N)%N;
                if (longest[node] == 0) continue;
                while (first == node || !canStart[first]) {
                    first = (first + d + N)%N;
                    lenFirst++;
                }
                if (lenFirst >= N) break;
                for (int nxt : adj[node]) {
                    if (!between(second, nxt, node, d)) {
                        longest[nxt] = max(longest[nxt], longest[node] + 1);
                    }
                    if (between(node, nxt, second, d) && between(node, first, nxt, d) && first != nxt && second != nxt && node != first) {
                        if (ans < longest[node] + 1 + dp[nxt][(first + d + N)%N][dDp^1]) {
                            ans = longest[node] + 1 + dp[nxt][(first + d + N)%N][dDp^1];
                            iAns = first+1;
                        }
                        if (ans < longest[node] + 1 + dp[nxt][(second - d + N)%N][dDp]) {
                            ans = longest[node] + 1 + dp[nxt][(second - d + N)%N][dDp];
                            iAns = first+1;
                        }
                    }
                }
            }
            // cerr << second << ":  ";
            // for (int i = 0; i < N; i++) cerr << longest[i] << " ";
            // cerr << "\n";
        }
    }
    assert(type == 1);
    cout << ans << "\n" << iAns << "\n";
}

• Subtask 1: 95 / 100