Submission #101633

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
101633	2019-03-19T05:40:14 Z	choikiwon	Sailing Race (CEOI12_race)	C++17	75 / 100	3000 ms	6528 KB

race

#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;
    if(t) {
        for(int i = (u + 1) % N; i != v; i = (i + 1) % N) {
            if(adj[u][i]) {
                ret = max(ret, dp1(u, i, 0) + 1);
                ret = max(ret, dp1(i, v, 1) + 1);
            }
        }
    }
    else {
        for(int i = (u + 1) % N; i != v; i = (i + 1) % N) {
            if(adj[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() {
    //freopen("input.txt", "r", stdin);

    std::ios::sync_with_stdio(false);

    cin >> N >> T;

    for(int i = 0; i < N; i++) {
        while(1) {
            int t; cin >> t;
            if(!t) break;
            t--;

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

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

    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));
                    }
                }
            }
        }
    }
    //*/

    cout << ans << '\n' << p + 1;
}

Subtask #1

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	5248 KB	Output is correct
2	Correct	7 ms	5248 KB	Output is correct
3	Correct	8 ms	5220 KB	Output is correct
4	Correct	11 ms	5248 KB	Output is correct
5	Correct	9 ms	5248 KB	Output is correct
6	Correct	19 ms	5248 KB	Output is correct
7	Correct	12 ms	5248 KB	Output is correct
8	Correct	31 ms	5376 KB	Output is correct
9	Correct	17 ms	5376 KB	Output is correct
10	Correct	22 ms	5376 KB	Output is correct
11	Correct	27 ms	5376 KB	Output is correct
12	Correct	457 ms	5652 KB	Output is correct
13	Correct	1384 ms	5952 KB	Output is correct
14	Correct	589 ms	6136 KB	Output is correct
15	Execution timed out	3023 ms	6380 KB	Time limit exceeded
16	Execution timed out	3033 ms	6520 KB	Time limit exceeded
17	Execution timed out	3028 ms	6400 KB	Time limit exceeded
18	Correct	975 ms	6392 KB	Output is correct
19	Execution timed out	3035 ms	6520 KB	Time limit exceeded
20	Execution timed out	3015 ms	6528 KB	Time limit exceeded