Submission #1184942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184942		vux2code	Sailing Race (CEOI12_race)	C++20	55 / 100	3094 ms	4684 KiB

race

// Src : Vux2Code
/* Note :
    https://oj.uz/problem/view/CEOI12_race
    
*/

#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 int 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, f1 [maxN] [maxN] [2], f2 [maxN] [maxN] [2];
vector <ll> adj [maxN];

ll nx (ll x) {
    x ++;
    if (x > n) x -= n;
    return x;
}

bool irg (ll st, ll en, ll x) {
    if (st == en || en == nx (st)) return 0;
    if (st > en) return x > st || x < en;
    return st < x && x < en;
}

bool inrange (ll st, ll en, bool dir, ll x) {
    if (dir) return irg (st, en, x);
    return irg (en, st, x);
}

ll fin2d (ll st, ll en, bool dir) {
    if (f1 [st] [en] [dir] != -1) return f1 [st] [en] [dir];
    f1 [st] [en] [dir] = 0;
    for (ll i : adj [st]) if (inrange (st, en, dir, i)) {
        maxi (f1 [st] [en] [dir], 1ll + max (fin2d (i, en, dir), fin2d (i, st, !dir)));
    }
    // cerr << st << ' ' << en << ' ' << dir << ' ' << f1 [st] [en] [dir] << '\n';
    return f1 [st] [en] [dir];
}

ll finz (ll st, ll en, bool dir) {
    if (f2 [st] [en] [dir] != -1) return f2 [st] [en] [dir];
    if (st == en) return f2 [st] [en] [dir] = 1;
    f2 [st] [en] [dir] = -inf64;
    for (ll i : adj [st]) if (inrange (st, en, dir, i) || i == en) maxi (f2 [st] [en] [dir], finz (i, en, dir) + 1);
    return f2 [st] [en] [dir];
}

ll fin1d (ll st, ll en, bool dir) {
    ll ans = 0;
    for (int i = 1; i <= n; i ++) if (inrange (st, en, dir, i)) {
        if (finz (st, i, dir) > 0) {
            for (ll j : adj [i]) {
                if (inrange (st, en, dir, j)) continue;
                maxi (ans, finz (st, i, dir) + fin2d (j, st, dir));
                maxi (ans, finz (st, i, dir) + fin2d (j, en, !dir));
            }
        }
    }
    return ans;
}
    

void solve () {
    cin >> n >> k;
    memset (f1, -1, sizeof f1);
    memset (f2, -1, sizeof f2);
    for (int i = 1, x; i <= n; i ++) {
        while (cin >> x && x > 0) adj [i]. pusb (x);
    }
    pll ans = {1, 1};
    // cerr << fin2d (4, 5, 0) << ' ' << fin2d (4, 5, 1) << '\n';
    for (int i = 1; i <= n; i ++) {
        for (ll j : adj [i]) {
            if (k) {
                if (ans. fi < 2 + fin1d (j, i, 0)) ans = {2 + fin1d (j, i, 0), i};
                if (ans. fi < 2 + fin1d (j, i, 1)) ans = {2 + fin1d (j, i, 1), i};
            }
            else {
                if (ans. fi < 2 + fin2d (j, i, 0)) ans = {2 + fin2d (j, i, 0), i};
                if (ans. fi < 2 + fin2d (j, i, 1)) ans = {2 + fin2d (j, i, 1), i};
                // cerr << i << ' ' << j << ' ' << ans. fi << '\n';
            }
        }
    }
    cout << ans. fi - 1 << '\n' << ans. se << '\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 ();
}

Compilation message (stderr)

race.cpp:23:47: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   23 | const ll maxN = 5e2 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;
      |                                               ^~~~

• Subtask 1: 55 / 100