oj.uz

답안 #1106887

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106887 2024-10-31T08:42:44 Z Zero_OP Sailing Race (CEOI12_race) C++14
40 / 100
 1058 ms 14524 KB 
#include <bits/stdc++.h>

using namespace std;

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        } return false;
    }

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, K;
    cin >> N >> K;
    vector<vector<int>> adj(N);
    vector<vector<bool>> e(N, vector<bool>(N));

    for(int i = 0, j; i < N; ++i){
        while(cin >> j){
            if(!j) break;
            --j;
            adj[i].push_back(j);
            e[i][j] = 1;
        }
    }

    vector<vector<vector<int>>> f(N, vector<vector<int>>(N, vector<int>(2, -1)));

    function<int(int, int, int)> dp = [&](int l, int r, int x){
        if(f[l][r][x] != -1) return f[l][r][x];
        int& ret = f[l][r][x]; ret = 0;

        for(int i = (l + 1) % N; i != r; i = (i + 1) % N){
            if(x == 0){
                if(e[l][i]){
                    maximize(ret, dp(l, i, 1) + 1);
                    maximize(ret, dp(i, r, 0) + 1);
                }
            } else{
                if(e[r][i]){
                    maximize(ret, dp(i, r, 0) + 1);
                    maximize(ret, dp(l, i, 1) + 1);
                }
            }
        }

        return ret;
    };

    pair<int, int> answer = {0, 0};
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            if(e[i][j]){
                maximize(answer, {dp(i, j, 1) + 1, i});
                maximize(answer, {dp(j, i, 0) + 1, i});
            }
        }
    }

    cout << answer.first << ' ' << answer.second + 1 << '\n';

    return 0;
}

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Incorrect 1 ms 504 KB Output isn't correct
5 Correct 2 ms 592 KB Output is correct
6 Incorrect 2 ms 592 KB Output isn't correct
7 Correct 5 ms 592 KB Output is correct
8 Incorrect 3 ms 592 KB Output isn't correct
9 Correct 8 ms 848 KB Output is correct
10 Correct 13 ms 1020 KB Output is correct
11 Correct 10 ms 1060 KB Output is correct
12 Incorrect 56 ms 2640 KB Output isn't correct
13 Incorrect 149 ms 5456 KB Output isn't correct
14 Correct 331 ms 9296 KB Output is correct
15 Incorrect 856 ms 14416 KB Output isn't correct
16 Incorrect 922 ms 14416 KB Output isn't correct
17 Incorrect 918 ms 14416 KB Output isn't correct
18 Correct 573 ms 14328 KB Output is correct
19 Incorrect 1058 ms 14416 KB Output isn't correct
20 Incorrect 1018 ms 14524 KB Output isn't correct