Submission #62701

#	Time	Username	Problem	Language	Result	Execution time	Memory
62701		eriksuenderhauf	Sailing Race (CEOI12_race)	C++11	90 / 100	3035 ms	7808 KiB

race

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 5e2 + 5;
const double eps = 1e-9;
int ans[MAXN], mx[MAXN][MAXN][2];
int dp[MAXN][MAXN][2], dp2[MAXN][MAXN][2];
bool adj[MAXN][MAXN];
int n;

int pr(int& x)
{
    x--;
    if (x < 1) x += n;
}

int nx(int& x)
{
    x++;
    if (x > n) x -= n;
}

int norm(int x)
{
    if (x < 1) return x + n;
    if (x > n) return x - n;
    return x;
}

int solve(int l, int r, int k) // path ends at r, interval at l
{
    if (dp[l][r][k] != -1)
        return dp[l][r][k];
    int ret = 0;
    if (k) { // ccw
        for (int i = norm(r + 1); i != l; nx(i))
            if (adj[r][i])
                ret = max(ret, max(solve(r, i, 0),  solve(l, i, 1)) + 1);
    } else { // cw
        for (int i = norm(l + 1); i != r; nx(i))
            if (adj[r][i])
                ret = max(ret, max(solve(r, i, 1), solve(l, i, 0)) + 1);
    }
    return dp[l][r][k] = ret;
}

int f2(int l, int r, int k)
{
    if (l == r)
        return 0;
    if (dp2[l][r][k] != -1)
        return dp2[l][r][k];
    int ret = adj[l][r] ? 0 : -INF;
    if (k) {
        for (int i = norm(r + 1); i != l; nx(i))
            if (adj[l][i])
                ret = max(ret, f2(i, r, 1));
    } else {
        for (int i = norm(l + 1); i != r; nx(i))
            if (adj[l][i])
                ret = max(ret, f2(i, r, 0));
    }
    return dp2[l][r][k] = ret + 1;
}

int main()
{
    for (int i = 0; i < MAXN; i++)
        for (int j = 0; j < MAXN; j++)
            dp[i][j][0] = dp[i][j][1] = -1,
            dp2[i][j][0] = dp2[i][j][1] = -1;
    int k;
    ni(n), ni(k);
    for (int i = 1; i <= n; i++)
    {
        for (;;)
        {
            int x;
            ni(x);
            if (x == 0)
                break;
            adj[i][x] = 1;
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (!adj[i][j])
                continue;
            ans[i] = max(ans[i], solve(i, j, 0) + 1);
            ans[i] = max(ans[i], solve(i, j, 1) + 1);
        }
    for (int i = 1; k == 1 && i <= n; i++)
    {
        memset(mx, 0, sizeof mx);
        for (int x = norm(i + 1); x != i; nx(x))
            for (int y = norm(x + 2); y != i; nx(y))
                if (adj[i][norm(y - 1)])
                    mx[x][y][0] = max(solve(x, norm(y - 1), 0) + 1, mx[x][norm(y - 1)][0]);
                else
                    mx[x][y][0] = max(0, mx[x][norm(y - 1)][0]);
        for (int x = norm(i - 1); x != i; pr(x))
            for (int y = norm(x - 2); y != i; pr(y))
                if (adj[i][norm(y + 1)])
                    mx[y][x][1] = max(solve(x, norm(y + 1), 1) + 1, mx[norm(y + 1)][x][1]);
                else
                    mx[y][x][1] = max(0, mx[norm(y + 1)][x][1]);

        for (int l = norm(i + 1); l != norm(i - 2); nx(l))
            for (int j = norm(l + 2); j != i; nx(j))
                if (adj[l][j])
                {
                    ans[l] = max(ans[l], f2(j, i, 0) + mx[l][j][0] + 1);
                    ans[l] = max(ans[l], f2(j, i, 0) + mx[l][j][1] + 1);
                }
        for (int l = norm(i + 1); l != norm(i - 2); nx(l))
            for (int j = norm(l + 2); j != i; nx(j))
                if (adj[j][l])
                {
                    ans[j] = max(ans[j], f2(l, i, 1) + mx[l][j][0] + 1);
                    ans[j] = max(ans[j], f2(l, i, 1) + mx[l][j][1] + 1);
                }
    }
    int ind = 0;
    for (int i = 1; i <= n; i++)
        if (ans[ind] < ans[i])
            ind = i;
    printf("%d\n%d\n", ans[ind], ind);
    return 0;
}

Compilation message (stderr)

race.cpp: In function 'int pr(int&)':
race.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
race.cpp: In function 'int nx(int&)':
race.cpp:45:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
race.cpp: In function 'int main()':
race.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     ni(n), ni(k);
          ^
race.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
race.cpp:7:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
race.cpp:103:13: note: in expansion of macro 'ni'
             ni(x);
             ^~

• Subtask 1: 90 / 100