답안 #101528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101528	2019-03-19T03:43:54 Z	choikiwon	Sailing Race (CEOI12_race)	C++17	30 / 100	3000 ms	6444 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;
    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);
                    ~~~~~^~~~~~~~~~

Subtask #1

30.0 / 100.0

#	결과	실행 시간	메모리	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