Submission #1261852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261852		_filya_	Sailing Race (CEOI12_race)	C++20	0 / 100	260 ms	4808 KiB

race

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 501;
int dp[N][N][2];
vector<int> G[N];

int solve_dp(int u, int v, bool state) {
    if (u == v) return dp[u][v][state] = 0;
    if (dp[u][v][state] != -1) return dp[u][v][state];
    int l = min(u, v), r = max(u, v);
    if (state) {
        for (auto w : G[r]) {
            if (l < w && w < r) {
                dp[u][v][1] = max(dp[u][v][1], solve_dp(u, w, 1) + 1);
                dp[u][v][1] = max(dp[u][v][1], solve_dp(v, w, 1) + 1);
            }
        }
    } else {
        for (auto w : G[r]) {
            if (!(l < w && w < r)) {
                if (w > v) {
                    dp[u][v][0] = max(dp[u][v][0], solve_dp(v, w, 1) + 1);
                } else {
                    dp[u][v][0] = max(dp[u][v][0], solve_dp(v, w, 0) + 1);
                }
                if (w > u) {
                    dp[u][v][0] = max(dp[u][v][0], solve_dp(u, w, 1) + 1);
                } else {
                    dp[u][v][0] = max(dp[u][v][0], solve_dp(u, w, 0) + 1);
                }
            }
        }
    }
    return dp[u][v][state];
}

int main()
{
// 	ifstream cin("input.txt");
//     ofstream cout("output.txt");
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int n, k; cin >> n >> k;
    set<pair<int, int>> edges;
    for (int i = 0; i < n; i++) {
        while(true) {
            int u; cin >> u;
            if (!u) break;
            u--;
            G[i].push_back(u);
            edges.insert({i, u});
        }
    }
    memset(dp, -1, sizeof dp);
    int ans = 0;
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            for (int state = 0; state < 2; state++) {
                dp[u][v][state] = solve_dp(u, v, state);
                if (edges.count({u, v})) ans = max(ans, dp[u][v][state]);
            }
        }
    }
    cout << ans << '\n';
}

• Subtask 1: 0 / 100