Submission #101587

#	Time	Username	Problem	Language	Result	Execution time	Memory
101587		choikiwon	Sailing Race (CEOI12_race)	C++17	65 / 100	3096 ms	5800 KiB

race

#include<bits/stdc++.h>
using namespace std;

const int MN = 555;

int N, T;
int adj[MN][MN];
int dp1[MN][MN][2], dp2[MN][MN][2];

int main() {
    scanf("%d %d", &N, &T);

    for(int i = 0; i < N; i++) {
        while(1) {
            int t; scanf("%d", &t);
            if(!t) break;
            t--;

            adj[i][t] = 1;
        }
    }

    for(int d = 1; d < N; d++) {
        for(int u = 0; u < N; u++) {
            int v = (u + d) % N;
            for(int t = 0; t < 2; t++) {
                int &ret = dp1[u][v][t];
                for(int i = (u + 1) % N; i != v; i = (i + 1) % N) {
                    if(adj[ (t? u : v) ][i]) {
                        ret = max(ret, dp1[u][i][0] + 1);
                        ret = max(ret, dp1[i][v][1] + 1);
                    }
                }
            }
        }
    }

    for(int i = 0; i < N; i++) dp2[i][i][0] = dp2[i][i][1] = 0;
    for(int d = 1; d < N; d++) {
        for(int u = 0; u < N; u++) {
            for(int t = 0; t < 2; t++) {
                int v = t? (u + d) % N : (u + N - d) % N;
                int &ret = dp2[u][v][t] = -1e9;

                if(t) {
                    for(int i = (u + 1) % N;; i = (i + 1) % N) {
                        if(adj[u][i]) {
                            ret = max(ret, dp2[i][v][1] + 1);
                        }
                        if(i == v) break;
                    }
                }
                else {
                    for(int i = (u + N - 1) % N;; i = (i + N - 1) % N) {
                        if(adj[u][i]) {
                            ret = max(ret, dp2[i][v][0] + 1);
                        }
                        if(i == v) break;
                    }
                }
            }
        }
    }

    int ans = 0;
    int p = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) if(i != j && adj[i][j]) {
            if(ans < dp1[i][j][0] + 1) {
                ans = dp1[i][j][0] + 1;
                p = i;
            }
            if(ans < dp1[j][i][1] + 1) {
                ans = dp1[j][i][1] + 1;
                p = i;
            }
        }
    }

    //*
    if(T) {
        for(int i = 0; i < N; i++) {
            vector<int> mx(N, -1e9);

            for(int j = (i + 1) % N; j != i; j = (j + 1) % N) {
                if(adj[i][j]) {
                    for(int k = (j + 1) % N; k != i; k = (k + 1) % N) {
                        if(ans < dp2[j][k][1] + 2 + mx[k]) {
                            ans = dp2[j][k][1] + 2 + mx[k];
                            p = i;
                        }
                    }
                }
                for(int k = (j + 1) % N; k != i; k = (k + 1) % N) {
                    if(adj[k][j]) {
                        mx[k] = max(mx[k], dp1[i][j][0]);
                    }
                }
            }

            mx = vector<int>(N, -1e9);
            for(int j = (i + N - 1) % N; j != i; j = (j + N - 1) % N) {
                if(adj[i][j]) {
                    for(int k = (j + N - 1) % N; k != i; k = (k + N - 1) % N) {
                        if(ans < dp2[j][k][0] + 2 + mx[k]) {
                            ans = dp2[j][k][0] + 2 + mx[k];
                            p = i;
                        }
                    }
                }
                for(int k = (j + N - 1) % N; k != i; k = (k + N - 1) % N) {
                    if(adj[k][j]) {
                        mx[k] = max(mx[k], dp1[j][i][1]);
                    }
                }
            }
        }

        for(int i = 0; i < N; i++) {
            vector<int> mx(N, -1e9);

            for(int j = (i + N - 1) % N; j != i; j = (j + N - 1) % N) {
                if(adj[j][i]) {
                    for(int k = (i + 1) % N; k != j; k = (k + 1) % N) {
                        if(ans < dp2[i][k][1] + 2 + mx[k]) {
                            ans = dp2[i][k][1] + 2 + mx[k];
                            p = j;
                        }
                    }
                }
                for(int k = (i + 1) % N; k != j; k = (k + 1) % N) {
                    if(adj[k][j]) {
                        mx[k] = max(mx[k], dp1[j][i][1]);
                    }
                }
            }

            mx = vector<int>(N, -1e9);
            for(int j = (i + 1) % N; j != i; j = (j + 1) % N) {
                if(adj[j][i]) {
                    for(int k = (i + N - 1) % N; k != j; k = (k + N - 1) % N) {
                        if(ans < dp2[i][k][0] + 2 + mx[k]) {
                            ans = dp2[i][k][0] + 2 + mx[k];
                            p = j;
                        }
                    }
                }
                for(int k = (i + N - 1) % N; k != j; k = (k + N - 1) % N) {
                    if(adj[k][j]) {
                        mx[k] = max(mx[k], dp1[i][j][0]);
                    }
                }
            }
        }
    }
    //*/

    printf("%d\n%d", ans, p + 1);
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &T);
     ~~~~~^~~~~~~~~~~~~~~~~
race.cpp:15:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int t; scanf("%d", &t);
                    ~~~~~^~~~~~~~~~

• Subtask 1: 65 / 100