Submission #1259623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259623		mtshasta	Sailing Race (CEOI12_race)	C++20	5 / 100	2307 ms	4668 KiB

race

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

const int MAXN = 505;
const int INF = -1e9;

int n, k;
vector<int> adj[MAXN];
int dp[MAXN][MAXN][2]; // dp[i][j][dir] = max length from i to j in direction dir
int best[MAXN][MAXN][2]; // best[i][j][dir] = max length starting at i, going dir, ending at j or beyond

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> k;
    
    // Read adjacency list
    for (int i = 0; i < n; i++) {
        int x;
        while (cin >> x && x != 0) {
            adj[i].push_back(x - 1);
        }
    }
    
    // Initialize DP arrays
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j][0] = dp[i][j][1] = INF;
            best[i][j][0] = best[i][j][1] = INF;
        }
    }
    
    // Base case: direct shortcuts
    for (int i = 0; i < n; i++) {
        for (int next : adj[i]) {
            dp[i][next][0] = dp[i][next][1] = 1;
        }
    }
    
    // Compute DP for all intervals
    for (int len = 1; len < n; len++) {
        for (int i = 0; i < n; i++) {
            int j = (i + len) % n;
            int j_rev = (i - len + n) % n;
            
            // Clockwise direction
            if (find(adj[i].begin(), adj[i].end(), j) != adj[i].end()) {
                dp[i][j][1] = 1;
            }
            
            // Try splitting the interval
            for (int mid = (i + 1) % n; mid != j; mid = (mid + 1) % n) {
                dp[i][j][1] = max(dp[i][j][1], dp[i][mid][1] + dp[mid][j][1]);
            }
            
            // Counterclockwise direction  
            if (find(adj[i].begin(), adj[i].end(), j_rev) != adj[i].end()) {
                dp[i][j_rev][0] = 1;
            }
            
            for (int mid = (i - 1 + n) % n; mid != j_rev; mid = (mid - 1 + n) % n) {
                dp[i][j_rev][0] = max(dp[i][j_rev][0], dp[i][mid][0] + dp[mid][j_rev][0]);
            }
        }
    }
    
    // Compute best arrays (allowing shortcuts at end)
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int dir = 0; dir < 2; dir++) {
                best[i][j][dir] = dp[i][j][dir];
                
                if (dp[i][j][dir] > INF) {
                    // Try using shortcuts from j
                    for (int next : adj[j]) {
                        int next_pos = dir ? (j + 1) % n : (j - 1 + n) % n;
                        best[i][j][dir] = max(best[i][j][dir], 
                                            dp[i][j][dir] + best[next][next_pos][1-dir]);
                    }
                }
            }
        }
    }
    
    int ans_len = 0, ans_pos = 0;
    
    // Find maximum without cycles
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int dir = 0; dir < 2; dir++) {
                if (best[i][j][dir] > ans_len) {
                    ans_len = best[i][j][dir];
                    ans_pos = i;
                }
            }
        }
    }
    
    // If k=1, try to form cycles
    if (k == 1) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int dir = 0; dir < 2; dir++) {
                    if (dp[i][j][dir] <= 0) continue;
                    
                    // Try to close the cycle
                    for (int back : adj[j]) {
                        if (find(adj[back].begin(), adj[back].end(), i) != adj[back].end()) {
                            int cycle_len = dp[i][j][dir] + 2;
                            if (cycle_len > ans_len) {
                                ans_len = cycle_len;
                                ans_pos = back;
                            }
                        }
                    }
                }
            }
        }
    }
    
    cout << ans_len << "\n" << ans_pos + 1 << "\n";
    
    return 0;
}

• Subtask 1: 5 / 100