Submission #1146476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146476		polarity	Sailing Race (CEOI12_race)	C++20	40 / 100	555 ms	14464 KiB

race

/**
 * Solution by 1egend (polarity.sh)
 * Date: 2025-02-05
 * Contest: CEOI 2012
 * Problem: race
**/

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

using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
#define pb push_back
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;

int n, k;
vector<vector<vi>> dp;
vector<vi> adj;

int idx(int i){
    if (i < 0){
        return n + (i % n);
    }

    return i % n;
}

int rec(int i, int j, int dir){
    if (i == j){
        return 1;
    }

    if (dp[i][j][dir] != 0){
        return dp[i][j][dir];
    }

    int mx = 1;
    if (dir == 1){
        int jj = j < i ? j + n : j;

        for (int k : adj[i]){
            int kk = k < i ? k + n:k;
            if (kk > jj){
                continue;
            }
            mx = max(mx, 1 + rec(idx(kk), idx(i + 1), 0));
            mx = max(mx, 1 + rec(idx(kk), idx(jj), 1));
        }
    } else {
        int ii = i < j ? i + n : i;

        for (int k : adj[i]){
            int kk = k < j ? k + n:k;
            if (kk > ii){
                continue;
            }
            mx = max(mx, 1 + rec(idx(kk), idx(i - 1), 1));
            mx = max(mx, 1 + rec(idx(kk), idx(j), 0));
        }
    }
    

    return dp[i][j][dir] = mx;
}

void solve(){
    cin >> n >> k;

    adj = vector<vi>(n);

    rep(i, 0, n){
        while (true){
            int x;
            cin >> x;
            if (x == 0){
                break;
            }

            --x;
            if (k == 0){
                adj[i].pb(x);
            } else {
                adj[x].pb(i);
            }
        }
    }

    dp = vector<vector<vi>>(n, vector<vi>(n, {0, 0}));

    rep(i, 0, n){
        rep(j, 0, n){
            rep(c, 0, 2){
                rec(i, j, c);
            }
        }
    }

    if (k == 0){
        int ans = 0;
        int ans_i = -1;

        rep(i, 0, n){
            if (dp[i][idx(i - 1)][1] > ans){
                ans = dp[i][idx(i - 1)][1];
                ans_i = i;
            }
        }

        cout << ans - 1 << endl;
        cout << ans_i + 1 << endl;
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 40 / 100