제출 #116071

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
116071		evpipis	Sailing Race (CEOI12_race)	C++98	100 / 100	564 ms	5752 KiB

race

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
const int len = 503;
int dp[len][len][2], mat[len][len], adis[len][len], cdis[len][len];
vector<int> adj[len];

bool ins(int a, int b, int c){
    return ((a < c && c < b) || (a > b && (a < c || c < b)));
}

int main(){
    int n, tp;
    scanf("%d %d", &n, &tp);
    for (int i = 0; i < n; i++){
        while (true){
            int temp;
            scanf("%d", &temp);

            if (!temp)
                break;

            adj[i].pb(temp-1);
            mat[i][temp-1] = 1;
        }
    }

    int ans = 0, st = 0;
    for (int sz = 1; sz <= n-1; sz++){
        for (int a = 0; a < n; a++){
            int b = (a+sz)%n;

            /*if ((n+b-a)%n > n/2){
                dp[a][b][0] = dp[b][a][1];
                dp[a][b][1] = dp[b][a][0];
                continue;
            }*/

            for (int j = 0; j < adj[a].size(); j++){
                int v = adj[a][j];
                if (ins(a, b, v))
                    dp[a][b][0] = max(dp[a][b][0], max(dp[a][v][1], dp[v][b][0])+1);
            }

            for (int j = 0; j < adj[b].size(); j++){
                int v = adj[b][j];
                if (ins(a, b, v))
                    dp[a][b][1] = max(dp[a][b][1], max(dp[a][v][1], dp[v][b][0])+1);
            }

            if (mat[b][a] && dp[a][b][0]+1 > ans)
                ans = dp[a][b][0]+1, st = b;
            if (mat[a][b] && dp[a][b][1]+1 > ans)
                ans = dp[a][b][1]+1, st = a;
        }
    }

    //printf("ans  = %d, st = %d\n", ans, st);
    if (tp == 0 || ans == n-1){
        printf("%d\n%d\n", ans, st+1);
        return 0;
    }

    for (int sz = 1; sz <= n-1; sz++){
        for (int a = 0; a < n; a++){
            int b = (a+sz)%n;
            if (mat[a][b])
                adis[a][b] = 1;
            for (int j = 0; j < adj[a].size(); j++){
                int v = adj[a][j];
                if (ins(a, b, v) && adis[v][b])
                    adis[a][b] = max(adis[a][b], adis[v][b]+1);
            }

            b = (a+n-sz)%n;
            if (mat[a][b])
                cdis[a][b] = 1;
            for (int j = 0; j < adj[a].size(); j++){
                int v = adj[a][j];
                if (ins(b, a, v) && cdis[v][b])
                    cdis[a][b] = max(cdis[a][b], cdis[v][b]+1);
            }
        }
    }

    for (int b = 0; b < n; b++){
        for (int c = 0; c < n; c++){
            if (c == b || adis[b][c] == 0)
                continue;

            int a = -1;
            for (int j = (c+1)%n; j != b; j = (j+1)%n){
                if (mat[j][b]){
                    a = j;
                    break;
                }
            }

            if (a == -1)
                continue;

            for (int j = 0; j < adj[c].size(); j++){
                int v = adj[c][j];
                if (ins(a, b, v) && adis[b][c]+max(dp[a][v][1], dp[v][b][0])+2 > ans)
                    ans = adis[b][c]+max(dp[a][v][1], dp[v][b][0])+2, st = a;
                    //printf("a = %d, b = %d, c = %d, v = %d, ans = %d\n", a+1, b+1, c+1, v+1, adis[b][c]+max(dp[a][v][1], dp[v][b][0])+2);
            }
        }
    }

    for (int b = 0; b < n; b++){
        for (int c = 0; c < n; c++){
            if (c == b || cdis[b][c] == 0)
                continue;

            int a = -1;
            for (int j = (c+n-1)%n; j != b; j = (j+n-1)%n){
                if (mat[j][b]){
                    a = j;
                    break;
                }
            }

            if (a == -1)
                continue;

            for (int j = 0; j < adj[c].size(); j++){
                int v = adj[c][j];

                if (ins(b, a, v) && cdis[b][c]+max(dp[b][v][1], dp[v][a][0])+2 > ans)
                    ans = cdis[b][c]+max(dp[b][v][1], dp[v][a][0])+2, st = a;
                    //printf("a = %d, b = %d, c = %d, v = %d, ans = %d\n", a+1, b+1, c+1, v+1, cdis[b][c]+max(dp[b][v][1], dp[v][a][0])+2);
            }
        }
    }

    printf("%d\n%d\n", ans, st+1);
    return 0;
}
/*
7 1 5
5 0 2
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int main()':
race.cpp:40:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < adj[a].size(); j++){
                             ~~^~~~~~~~~~~~~~~
race.cpp:46:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < adj[b].size(); j++){
                             ~~^~~~~~~~~~~~~~~
race.cpp:70:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < adj[a].size(); j++){
                             ~~^~~~~~~~~~~~~~~
race.cpp:79:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < adj[a].size(); j++){
                             ~~^~~~~~~~~~~~~~~
race.cpp:103:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < adj[c].size(); j++){
                             ~~^~~~~~~~~~~~~~~
race.cpp:128:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < adj[c].size(); j++){
                             ~~^~~~~~~~~~~~~~~
race.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &tp);
     ~~~~~^~~~~~~~~~~~~~~~~~
race.cpp:19:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &temp);
             ~~~~~^~~~~~~~~~~~~

• Subtask 1: 100 / 100