Submission #1185305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185305		vux2code	Sailing Race (CEOI12_race)	C++20	100 / 100	871 ms	12568 KiB

race

// Src : Vux2Code
/* Note :
    Iamstupid
*/

#include <bits/stdc++.h>
#define fi first
#define se second
#define pusb push_back
#define popb pop_back
#define pusf push_front
#define popf pop_front

using namespace std;

// template <typename T> void vout(T s){ cout << s << endl; exit(0);}

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;

const ll maxN = 5e2 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;

void maxi (ll &x, ll y) {x = max (x, y);}
void mini (ll &x, ll y) {x = min (x, y);}

/* ---------HASHING-------- */
// const base = 31, mod2 = 1e9 + 9;

/* ---------BITMASK-------- */
// ll count (ll x) {return __builtin_popcountll (x);}
// ll fst (ll x) {return 63 - __builtin_clzll (x);}
// ll last (ll x) {return __builtin_ctzll (x);}
// bool bit (ll x, ll y) {return ((x >> y) & 1);}

ll t = 1;

ll n, k, nx [maxN] [2], dp [maxN] [maxN] [2], dp0 [maxN] [maxN] [2], dp1 [maxN] [maxN] [2], tmp, tmp2, n1, n2;
bool adj [maxN] [maxN];

void fin (ll st, ll en, bool dir) {
    if (adj [st] [en]) {
        dp0 [st] [en] [dir] = 1;
        dp1 [st] [en] [dir] = 1 + dp [en] [nx [st] [dir]] [!dir];
    }
    else {
        dp0 [st] [en] [dir] = -n;
        dp1 [st] [en] [dir] = -n;
    }
    tmp = nx [st] [dir];
    while (tmp != en) {
        maxi (dp0 [st] [en] [dir], dp0 [st] [tmp] [dir] + dp0 [tmp] [en] [dir]);
        maxi (dp1 [st] [en] [dir], dp0 [st] [tmp] [dir] + dp1 [tmp] [en] [dir]);
        tmp = nx [tmp] [dir];
    }
    dp [st] [en] [dir] = max (dp1 [st] [en] [dir], dp [st] [nx [en] [!dir]] [dir]);
}

void solve () {
    pll ans = {0, 0};
    cin >> n >> k;
    for (int i = 0, x; i < n; i ++) {
        while (cin >> x && x > 0) adj [i] [x - 1] = 1; 
    }
    for (int i = 0; i < n; i ++) {
        nx [i] [0] = (i - 1 + n) % n;
        nx [i] [1] = (i + 1) % n;
    }
    for (int len = 1; len < n; len ++) {
        for (int i = 0, j; i < n; i ++) {
            j = (i + len) % n;
            fin (i, j, 1);
            fin (j, i, 0);
        }
    }
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            for (int dir = 0; dir <= 1; dir ++) {
                if (ans. fi < dp1 [i] [j] [dir]) ans = {dp [i] [j] [dir], i};
            }
        }
    }
    if (k) {
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                for (int dir = 0; dir <= 1; dir ++) {
                    tmp = dp0 [i] [j] [dir];
                    if (tmp <= 0) continue;
                    n1 = nx [j] [dir];
                    while (n1 != i && !adj [n1] [i]) n1 = nx [n1] [dir];
                    if (n1 == i) continue;
                    for (n2 = nx [n1] [dir]; n2 != i; n2 = nx [n2] [dir]) {
                        if (adj [j] [n2]) {
                            tmp2 = max (dp [n2] [nx [n1] [dir]] [!dir],
                                        dp [n2] [nx [i] [!dir]] [dir]);
                            if (ans. fi < 2 + tmp + tmp2) {
                                ans = {2 + tmp + tmp2, n1};
                            }
                        }
                    }
                }
            }
        }
    }
    cout << ans. fi << '\n' << ans. se + 1 << '\n';
}

int main () {
    ios::sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);
    // #define TASK "E:/Code/CP/task"
    // if (fopen (TASK".inp", "r")) {
    //     freopen (TASK".inp", "r", stdin);
    //     freopen (TASK".out", "w", stdout);
    // }
    //cin >> t;
    while (t--) solve ();
}

• Subtask 1: 100 / 100