Submission #1261866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261866		_filya_	Sailing Race (CEOI12_race)	C++20	40 / 100	222 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] = 1;
    if (dp[u][v][state] != -1) return dp[u][v][state];
    dp[u][v][state] = 0;
    // if (u == 6 && v == 0 && state == 1) {
    //     cout << "bad" << '\n';
    // }
    int l = min(u, v), r = max(u, v);
    if (state) {
        for (auto w : G[v]) {
            if (l < w && w < r) {
                dp[u][v][1] = max(dp[u][v][1], solve_dp(u, w, 1));
                dp[u][v][1] = max(dp[u][v][1], solve_dp(v, w, 1));
            }
        }
    } else {
        for (auto w : G[v]) {
            if (w < l || w > r) {
                if (w > r) {
                    dp[u][v][0] = max(dp[u][v][0], solve_dp(r, w, 1));
                } else {
                    dp[u][v][0] = max(dp[u][v][0], solve_dp(r, w, 0));
                }
                if (w > l) {
                    dp[u][v][0] = max(dp[u][v][0], solve_dp(l, w, 0));
                } else {
                    dp[u][v][0] = max(dp[u][v][0], solve_dp(l, w, 1));
                }
            }
        }
    }
    dp[u][v][state] += 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;
    int start = 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 < dp[u][v][state]) {
                    ans = dp[u][v][state];
                    start = u;
                }
            }
        }
    }
    // for (int u = 0; u < n; u++) {
    //     for (int v = 0; v < n; v++) {

    //     }
    // }
    cout << ans << '\n';
    cout << start + 1 << '\n';
}

• Subtask 1: 40 / 100