답안 #101634

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101634 2019-03-19T05:42:10 Z choikiwon Sailing Race (CEOI12_race) C++17
75 / 100
3000 ms 6392 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;
    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;
}
# 결과 실행 시간 메모리 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