Submission #95439

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
95439	2019-02-01T08:14:53 Z	forestryks	Sailing Race (CEOI12_race)	C++14	40 / 100	566 ms	2808 KB

race

///////////////////////////////////////////////////////////////////////////////////////////////
#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];

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 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;
        }
    }

    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;
                }
            }
        }
    }

    // for (int i = 0; i < n; ++i) {
    //     for (int j = 0; j < n; ++j) {
    //         cout << ": " << i + 1 << ' ' << j + 1 << endl;
    //         cout << fc(i, j) << endl;
    //         cout << f(i, j) << endl;
    //     }
    // }

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

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Incorrect	2 ms	376 KB	Output isn't correct
3	Incorrect	2 ms	504 KB	Output isn't correct
4	Incorrect	2 ms	504 KB	Output isn't correct
5	Correct	3 ms	504 KB	Output is correct
6	Incorrect	3 ms	632 KB	Output isn't correct
7	Correct	5 ms	632 KB	Output is correct
8	Incorrect	4 ms	632 KB	Output isn't correct
9	Correct	7 ms	760 KB	Output is correct
10	Correct	9 ms	760 KB	Output is correct
11	Correct	9 ms	760 KB	Output is correct
12	Incorrect	36 ms	1272 KB	Output isn't correct
13	Incorrect	71 ms	1784 KB	Output isn't correct
14	Correct	140 ms	2192 KB	Output is correct
15	Incorrect	415 ms	2740 KB	Output isn't correct
16	Incorrect	500 ms	2776 KB	Output isn't correct
17	Incorrect	411 ms	2808 KB	Output isn't correct
18	Correct	218 ms	2652 KB	Output is correct
19	Incorrect	566 ms	2808 KB	Output isn't correct
20	Incorrect	564 ms	2808 KB	Output isn't correct