Submission #127025

#	Time	Username	Problem	Language	Result	Execution time	Memory
127025		eriksuenderhauf	Sailing Race (CEOI12_race)	C++11	75 / 100	3050 ms	7544 KiB

race

//#pragma GCC optimize("O3")
#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 + 2;
const int INF = 1e9 + 7;
int ans[MAXN], mx[MAXN][MAXN][2];
int dp[MAXN][MAXN][2], dp2[MAXN][MAXN][2];
int adj[MAXN][MAXN];
vi nex[MAXN];
int n;

bool between(int l, int r, int x) {
    if (l > r)
        return l < x || x < r;
    return l < x && x < r;
}

int solve(int l, int r, int k) {// path ends at r, interval at l
    if (~dp[l][r][k]) return dp[l][r][k];
    int &ret = dp[l][r][k];
    ret = 0;
    if (k) { // ccw
        //for (int i = (r%n) + 1; i != l; i = (i%n) + 1)
            //if (adj[r][i])
        for (int i: nex[r])
            if (between(r, l, i))
                ret = max(ret, max(solve(r, i, 0),  solve(l, i, 1)) + 1);
    } else { // cw
        //for (int i = (l%n) + 1; i != r; i = (i%n) + 1)
            //if (adj[r][i])
        for (int i: nex[r])
            if (between(l, r, i))
                ret = max(ret, max(solve(r, i, 1), solve(l, i, 0)) + 1);
    }
    return ret;
}

int f2(int l, int r, int k) {
    if (l == r)
        return 0;
    if (~dp2[l][r][k])
        return dp2[l][r][k];
    int ret = adj[l][r] ? 0 : -INF;
    if (k) {
        //for (int i = r%n+1; i != l; i = (i%n) + 1)
            //if (adj[l][i])
        for (int i: nex[l])
            if (between(r, l, i))
                ret = max(ret, f2(i, r, 1));
    } else {
        //for (int i = l%n+1; i != r; i = (i%n) + 1)
            //if (adj[l][i])
        for (int i: nex[l])
            if (between(l, r, i))
                ret = max(ret, f2(i, r, 0));
    }
    return dp2[l][r][k] = ret + 1;
}

int main() {
    memset(dp, -1, sizeof dp);
    memset(dp2, -1, sizeof dp2);
    int k;
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        while (1) {
            int x; ni(x);
            if (x == 0)
                break;
            adj[i][x] = 1;
            nex[i].pb(x);
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j: nex[i])
            ans[i] = max(ans[i], max(solve(i, j, 0), solve(i, j, 1)) + 1);
    if (k == 1) for (int i = 1; i <= n; i++) {
        for (int x = (i%n) + 1; x != i; x = (x%n) + 1)
            for (int y = (x+1)%n + 1; y != i; y = (y%n) + 1)
                if (adj[i][(y+n-2)%n + 1])
                    mx[x][y][0] = max(solve(x, (y+n-2)%n + 1, 0) + 1, mx[x][(y+n-2)%n + 1][0]);
                else
                    mx[x][y][0] = max(0, mx[x][(y+n-2)%n + 1][0]);
        for (int x = (i+n-2)%n+1; x != i; x = (x-2+n)%n+1)
            for (int y = (x+2*n-3)%n+1; y != i; y = (y-2+n)%n+1)
                if (adj[i][y%n+1])
                    mx[y][x][1] = max(solve(x, y%n+1, 1) + 1, mx[y%n+1][x][1]);
                else
                    mx[y][x][1] = max(0, mx[y%n+1][x][1]);

        for (int l = i%n+1; l != (i+2*n-3)%n+1; l = (l%n) + 1)
            for (int j = (l+1)%n+1; j != i; j = (j%n) + 1) {
                if (adj[l][j])
                    ans[l] = max(ans[l], max(f2(j, i, 0) + mx[l][j][0], f2(j, i, 0) + mx[l][j][1]) + 1);
                if (adj[j][l])
                    ans[j] = max(ans[j], max(f2(l, i, 1) + mx[l][j][0], 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 main()':
race.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
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:79:20: note: in expansion of macro 'ni'
             int x; ni(x);
                    ^~

• Subtask 1: 75 / 100