Submission #62702

#	Time	Username	Problem	Language	Result	Execution time	Memory
62702		eriksuenderhauf	Sailing Race (CEOI12_race)	C++11	85 / 100	3039 ms	6760 KiB

race

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define enl printf("\n")
#define ni(n) scanf("%d", &(n))
#define pri(n) printf("%d\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;
typedef long long ll;
const int MAXN = 5e2 + 5;
const int INF = 1e9 + 7;
int ans[MAXN], mx[MAXN][MAXN][2];
int dp[MAXN][MAXN][2], dp2[MAXN][MAXN][2];
bitset<MAXN> adj[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()
{
    //clock_t t = clock();
    //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;
    memset(dp, -1, sizeof dp);
    memset(dp2, -1, sizeof dp2);
    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);
        }
    if (k == 1) for (int i = 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);
                }
                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);
    //cout<<clock()-t<<"\n";
    return 0;
}

Compilation message (stderr)

race.cpp: In function 'int pr(int&)':
race.cpp:27:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
race.cpp: In function 'int nx(int&)':
race.cpp:33:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
race.cpp: In function 'int main()':
race.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     ni(n), ni(k);
          ^
race.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
race.cpp:4: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:92:13: note: in expansion of macro 'ni'
             ni(x);
             ^~

• Subtask 1: 85 / 100