oj.uz

Submission #95450

# Submission time Handle Problem Language Result Execution time Memory
95450 2019-02-01T08:43:55 Z forestryks Sailing Race (CEOI12_race) C++14
100 / 100
 1923 ms 4772 KB 
///////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout)
#define f first
#define s second
#define x1 x1qwer
#define y1 y1qwer
#define right right123
#define left left123
#define foreach(it, v) for (auto it : v)
#define rep(it, n) for (int it = 0; it < n; ++it)
#define forin(it, l, r) for (int it = l; it < r; ++it)
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double DINF = numeric_limits<double>::infinity();
const ll MOD = 1e9 + 7;
const double EPS = 1e-7;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
mt19937 mmtw_(MOD);
uniform_int_distribution<ll> rd_;
ll randomll() { return rd_(mmtw_);}
ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; }
////////////////////////////////////////////////////////////////////////////////////////////////

const int MAXN = 505;
int n, k;
bool g[MAXN][MAXN];
int dp[MAXN][MAXN];
int dpc[MAXN][MAXN];
int ds[MAXN][MAXN];
int dsc[MAXN][MAXN];

inline int md(int x) {
    if (x >= n) return x - n;
    if (x < 0) return x + n;
    return x;
}

int f(int, int);
int fc(int, int);

int f(int a, int b) {
    if (dp[a][b] != -1) return dp[a][b];

    dp[a][b] = 0;
    for (int i = md(b + 1); i != a; i = md(i + 1)) {
        if (g[b][i]) dp[a][b] = max(dp[a][b], max(fc(b, i), f(a, i)) + 1);
    }

    return dp[a][b];
}

int fc(int a, int b) {
    if (dpc[a][b] != -1) return dpc[a][b];

    dpc[a][b] = 0;
    for (int i = md(b - 1); i != a; i = md(i - 1)) {
        if (g[b][i]) dpc[a][b] = max(dpc[a][b], max(f(b, i), fc(a, i)) + 1);
    }

    return dpc[a][b];
}

int s(int a, int b) {
    if (ds[a][b] != -2) return ds[a][b];

    ds[a][b] = -1;
    if (a == b) ds[a][b] = 0;
    if (g[a][b]) ds[a][b] = 1;
    for (int i = md(a + 1); i != b; i = md(i + 1)) {
        int ai = s(a, i);
        int ib = s(i, b);
        if (ai == -1 || ib == -1) continue;
        ds[a][b] = max(ds[a][b], ai + ib);
    }

    return ds[a][b];
}

int sc(int a, int b) {
    if (dsc[a][b] != -2) return dsc[a][b];

    dsc[a][b] = -1;
    if (a == b) dsc[a][b] = 0;
    if (g[a][b]) dsc[a][b] = 1;
    for (int i = md(a - 1); i != b; i = md(i - 1)) {
        int ai = sc(a, i);
        int ib = sc(i, b);
        if (ai == -1 || ib == -1) continue;
        dsc[a][b] = max(dsc[a][b], ai + ib);
    }

    return dsc[a][b];
}

int main() {
    FAST_IO;
    cin >> n >> k;
    rep(i, n) {
        while (true) {
            int x;
            cin >> x;
            x--;
            if (x == -1) break;
            g[i][x] = true;
        }
    }

    rep(i, n) {
        rep(j, n) {
            dp[i][j] = dpc[i][j] = -1;
            ds[i][j] = dsc[i][j] = -2;
        }
    }

    int res = 0;
    int st = 0;
    rep(i, n) {
        rep(j, n) {
            if (i == j) continue;
            if (g[i][j]) {
                int nw = max(f(i, j), fc(i, j)) + 1;
                if (nw > res) {
                    res = nw;
                    st = i;
                }
            }
        }
    }

    if (k == 1) {
        rep(b, n) {
            rep(c, n) {
                if (b == c) continue;
                if (s(b, c) == -1) continue;

                int a;
                for (a = md(c + 1); a != b; a = md(a + 1)) {
                    if (g[a][b]) break;
                }

                if (a == b) continue;

                for (int d = md(a + 1); d != b; d = md(d + 1)) {
                    if (!g[c][d]) continue;
                    int nw = 2 + s(b, c) + max(f(b, d), fc(a, d));
                    if (nw > res) {
                        res = nw;
                        st = a;
                    }
                }
            }
        }

        rep(b, n) {
            rep(c, n) {
                if (b == c) continue;
                if (sc(b, c) == -1) continue;

                int a;
                for (a = md(c - 1); a != b; a = md(a - 1)) {
                    if (g[a][b]) break;
                }

                if (a == b) continue;

                for (int d = md(a - 1); d != b; d = md(d - 1)) {
                    if (!g[c][d]) continue;
                    int nw = 2 + sc(b, c) + max(fc(b, d), f(a, d));
                    if (nw > res) {
                        res = nw;
                        st = a;
                    }
                }
            }
        }
    }

    cout << res << endl;
    cout << st + 1 << endl;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 5 ms 888 KB Output is correct
7 Correct 5 ms 888 KB Output is correct
8 Correct 10 ms 1016 KB Output is correct
9 Correct 7 ms 1148 KB Output is correct
10 Correct 9 ms 1272 KB Output is correct
11 Correct 9 ms 1272 KB Output is correct
12 Correct 118 ms 2168 KB Output is correct
13 Correct 351 ms 2936 KB Output is correct
14 Correct 136 ms 3704 KB Output is correct
15 Correct 1684 ms 4772 KB Output is correct
16 Correct 1765 ms 4772 KB Output is correct
17 Correct 1658 ms 4728 KB Output is correct
18 Correct 226 ms 4600 KB Output is correct
19 Correct 1917 ms 4700 KB Output is correct
20 Correct 1923 ms 4740 KB Output is correct