Submission #101528

# Submission time Handle Problem Language Result Execution time Memory
101528 2019-03-19T03:43:54 Z choikiwon Sailing Race (CEOI12_race) C++17
30 / 100
3000 ms 6444 KB
#include<bits/stdc++.h>
using namespace std;

const int MN = 555;

int N, T;
int adj[MN][MN];

int cc1[MN][MN][2];
int dp1(int u, int v, int t) {
    int &ret = cc1[u][v][t];
    if(ret != -1) return ret;

    ret = 0;
    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);
        }
    }
    return ret;
}

int cc2[MN][MN][2];
int dp2(int u, int v, int t) {
    int &ret = cc2[u][v][t];
    if(ret != -1) return ret;
    if(u == v) return ret = 0;

    ret = -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;
        }
    }
    return ret;
}

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

    memset(cc1, -1, sizeof(cc1));
    memset(cc2, -1, sizeof(cc2));

    int ans = 0;
    int p = -1;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) if(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

race.cpp: In function 'int main()':
race.cpp:51: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:55:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int t; scanf("%d", &t);
                    ~~~~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5248 KB Output isn't correct
2 Correct 6 ms 5248 KB Output is correct
3 Incorrect 8 ms 5164 KB Output isn't correct
4 Incorrect 11 ms 5248 KB Output isn't correct
5 Incorrect 9 ms 5232 KB Output isn't correct
6 Incorrect 18 ms 5248 KB Output isn't correct
7 Correct 14 ms 5396 KB Output is correct
8 Incorrect 31 ms 5376 KB Output isn't correct
9 Correct 21 ms 5376 KB Output is correct
10 Correct 23 ms 5444 KB Output is correct
11 Correct 23 ms 5376 KB Output is correct
12 Correct 437 ms 5632 KB Output is correct
13 Incorrect 1340 ms 5868 KB Output isn't correct
14 Incorrect 740 ms 6088 KB Output isn't correct
15 Execution timed out 3005 ms 6380 KB Time limit exceeded
16 Execution timed out 3057 ms 6416 KB Time limit exceeded
17 Execution timed out 3019 ms 6376 KB Time limit exceeded
18 Incorrect 1472 ms 6316 KB Output isn't correct
19 Execution timed out 3074 ms 6444 KB Time limit exceeded
20 Execution timed out 3029 ms 6444 KB Time limit exceeded