Submission #101634

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
101634	2019-03-19T05:42:10 Z	choikiwon	Sailing Race (CEOI12_race)	C++17	75 / 100	3000 ms	6392 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) {
                for(int k = (j + 1) % N; k != i; k = (k + 1) % N) {
                    if(adj[i][j]) {
                        if(ans < dp2(j, k, 1) + 2 + mx[k]) {
                            ans = dp2(j, k, 1) + 2 + mx[k];
                            p = i;
                        }
                    }
                    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) {
                for(int k = (j + N - 1) % N; k != i; k = (k + N - 1) % N) {
                    if(adj[i][j]) {
                        if(ans <= dp2(j, k, 0) + 2 + mx[k]) {
                            ans = dp2(j, k, 0) + 2 + mx[k];
                            p = i;
                        }
                    }
                    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) {
                for(int k = (i + 1) % N; k != j; k = (k + 1) % N) {
                    if(adj[j][i]) {
                        if(ans <= dp2(i, k, 1) + 2 + mx[k]) {
                            ans = dp2(i, k, 1) + 2 + mx[k];
                            p = j;
                        }
                    }
                    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) {
                for(int k = (i + N - 1) % N; k != j; k = (k + N - 1) % N) {
                    if(adj[j][i]) {
                        if(ans <= dp2(i, k, 0) + 2 + mx[k]) {
                            ans = dp2(i, k, 0) + 2 + mx[k];
                            p = j;
                        }
                    }
                    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	9 ms	5248 KB	Output is correct
4	Correct	10 ms	5248 KB	Output is correct
5	Correct	9 ms	5248 KB	Output is correct
6	Correct	18 ms	5248 KB	Output is correct
7	Correct	11 ms	5376 KB	Output is correct
8	Correct	33 ms	5376 KB	Output is correct
9	Correct	19 ms	5404 KB	Output is correct
10	Correct	21 ms	5376 KB	Output is correct
11	Correct	24 ms	5452 KB	Output is correct
12	Correct	432 ms	5640 KB	Output is correct
13	Correct	1339 ms	6008 KB	Output is correct
14	Correct	585 ms	6136 KB	Output is correct
15	Execution timed out	3077 ms	6296 KB	Time limit exceeded
16	Execution timed out	3022 ms	6392 KB	Time limit exceeded
17	Execution timed out	3011 ms	6392 KB	Time limit exceeded
18	Correct	967 ms	6292 KB	Output is correct
19	Execution timed out	3041 ms	6280 KB	Time limit exceeded
20	Execution timed out	3047 ms	6272 KB	Time limit exceeded