oj.uz

답안 #95444

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95444 2019-02-01T08:37:33 Z forestryks Sailing Race (CEOI12_race) C++14
95 / 100
 1904 ms 4760 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;
                }
            }
        }
    }

    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
95.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Incorrect 4 ms 764 KB Output isn't correct
6 Correct 6 ms 888 KB Output is correct
7 Correct 9 ms 888 KB Output is correct
8 Correct 10 ms 1016 KB Output is correct
9 Correct 16 ms 1144 KB Output is correct
10 Correct 18 ms 1144 KB Output is correct
11 Correct 23 ms 1272 KB Output is correct
12 Correct 123 ms 2040 KB Output is correct
13 Correct 363 ms 2936 KB Output is correct
14 Correct 820 ms 3964 KB Output is correct
15 Correct 1701 ms 4528 KB Output is correct
16 Correct 1862 ms 4760 KB Output is correct
17 Correct 1880 ms 4728 KB Output is correct
18 Correct 1505 ms 4728 KB Output is correct
19 Correct 1904 ms 4744 KB Output is correct
20 Correct 1875 ms 4728 KB Output is correct