Submission #1107233

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1107233	2024-11-01T03:58:09 Z	Zero_OP	Sailing Race (CEOI12_race)	C++14	Compilation error	0 ms	0 KB

race

duma no cay vai #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>> e(N, vector<int>(N));
    for(int i = 0, j = 0; i < N; ++i){
        while(cin >> j){
            if(!j) break;
            --j;
            e[i][j] = 1;
        }
    }

    const int inf = 1e9;
    vector<vector<vector<int>>> dp(N, vector<vector<int>>(N, vector<int>(2, -inf)));
    vector<vector<vector<int>>> max_dp(N, vector<vector<int>>(N, vector<int>(2, -inf)));

    //dp[l][r][k] = maximum paths if we start at l, end at r and moving around range [l...r] in k-wise
    //max_dp[l][r][k] = maximum paths if we start at l end at somewhere but still moving around range [l...r] in k-wise

    for(int i = 0; i < N; ++i){
        dp[i][i][0] = dp[i][i][1] = max_dp[i][i][0] = max_dp[i][i][1] = 0;
    }

    vector<vector<int>> to(2, vector<int>(N));
    for(int i = 0; i < N; ++i){
        to[0][i] = (i + 1) % N;
        to[1][i] = (i + N - 1) % N;
    }

    auto solve = [&](int l, int r, int k){
        if(e[l][r]){
            maximize(dp[l][r][k], 1); //base-case
            maximize(max_dp[l][r][k], max_dp[r][to[k][l]][k ^ 1] + 1);  //case go back but not cut [l...r - 1]
        }

        for(int nxt = to[k][l]; nxt != r; nxt = to[k][nxt]){
            if(e[l][nxt]){
                maximize(dp[l][r][k], dp[l][nxt][k] + dp[nxt][r][k]);
                maximize(max_dp[l][r][k], dp[l][nxt][k] + max_dp[nxt][r][k]);
            }
        }

        maximize(max_dp[l][r][k], max_dp[l][to[k ^ 1][r]][k]);
    };

    for(int len = 1; len < N; ++len){
        for(int l = 0, r = len; l < N; ++l, r = (r + 1) % N){
            solve(l, r, 0);
            solve(r, l, 1);
        }
    }

    pair<int, int> res = {0, 0};
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            for(int k = 0; k < 2; ++k){
                maximize(res, make_pair(max_dp[i][j][k], i));
            }
        }
    }

    if(!K){
        cout << res.first << ' ' << res.second + 1 << '\n';
        return 0;
    }

    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            for(int k = 0; k < 2; ++k){
                if(dp[i][j][k] <= 0) continue;

                int bestS = to[k][j];
                while(bestS != i && !e[bestS][i]) bestS = to[k][bestS];
                if(bestS == i) continue;

                //just consider the first pos that in range [j+1...N-1] u [0...i - 1] that have edge with e[pos][i]
                //because when we move the j up, the range [i...j] will be extended and the max_dp[i][j][k] <= max_dp[i][to[k][j]][k]

                for(int candidate = to[k][bestS]; candidate != i; candidate = to[k][candidate]){ //choose the T
                    if(e[j][candidate]){ //S -> i -> ... -> j -> T -> ...
                        int last = max(max_dp[to[k][bestS]][candidate][k ^ 1], max_dp[candidate][to[k ^ 1][i]][k]); //some last paths
                        int solution = 1 + dp[i][j][k] + 1 + last;
                        cout << bestS << ' ' << i << ' ' << j << ' ' << candidate << '\n';
                        cout << "edge : " << candidate << ' ' << j << '\n';
                        cout << "this : " << solution << ' ' << last << ' ' << dp[i][j][k] << '\n';
                        cout << "debug for : " << i << ' ' << j << ' ' << k << ' ' << bestS << ' ' << candidate << '\n';
                        cout << "paths [i...j] in k-wise : " << dp[i][j][k] << '\n';
                        cout << "the first range (bestS...T] from T : " << max_dp[to[k][bestS]][candidate][k ^ 1] << '\n';
                        cout << "the second range [T...i) from T : " << max_dp[candidate][to[k ^ 1][i]][k] << '\n';
                        cout << '\n';
                        maximize(res, {solution, bestS});
                    }
                }
            }
        }
    }

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

    return 0;
}

Compilation message

race.cpp:1:17: error: stray '#' in program
    1 | duma no cay vai #include <bits/stdc++.h>
      |                 ^
race.cpp:1:1: error: 'duma' does not name a type
    1 | duma no cay vai #include <bits/stdc++.h>
      | ^~~~
race.cpp: In function 'int main()':
race.cpp:13:5: error: 'ios_base' has not been declared
   13 |     ios_base::sync_with_stdio(0); cin.tie(0);
      |     ^~~~~~~~
race.cpp:13:35: error: 'cin' was not declared in this scope
   13 |     ios_base::sync_with_stdio(0); cin.tie(0);
      |                                   ^~~
race.cpp:23:5: error: 'vector' was not declared in this scope
   23 |     vector<vector<int>> e(N, vector<int>(N));
      |     ^~~~~~
race.cpp:23:19: error: expected primary-expression before 'int'
   23 |     vector<vector<int>> e(N, vector<int>(N));
      |                   ^~~
race.cpp:28:13: error: 'e' was not declared in this scope
   28 |             e[i][j] = 1;
      |             ^
race.cpp:33:26: error: expected primary-expression before 'int'
   33 |     vector<vector<vector<int>>> dp(N, vector<vector<int>>(N, vector<int>(2, -inf)));
      |                          ^~~
race.cpp:34:26: error: expected primary-expression before 'int'
   34 |     vector<vector<vector<int>>> max_dp(N, vector<vector<int>>(N, vector<int>(2, -inf)));
      |                          ^~~
race.cpp:40:9: error: 'dp' was not declared in this scope
   40 |         dp[i][i][0] = dp[i][i][1] = max_dp[i][i][0] = max_dp[i][i][1] = 0;
      |         ^~
race.cpp:40:37: error: 'max_dp' was not declared in this scope
   40 |         dp[i][i][0] = dp[i][i][1] = max_dp[i][i][0] = max_dp[i][i][1] = 0;
      |                                     ^~~~~~
race.cpp:43:19: error: expected primary-expression before 'int'
   43 |     vector<vector<int>> to(2, vector<int>(N));
      |                   ^~~
race.cpp:45:9: error: 'to' was not declared in this scope
   45 |         to[0][i] = (i + 1) % N;
      |         ^~
race.cpp: In lambda function:
race.cpp:50:12: error: 'e' was not declared in this scope
   50 |         if(e[l][r]){
      |            ^
race.cpp:51:22: error: 'dp' was not declared in this scope
   51 |             maximize(dp[l][r][k], 1); //base-case
      |                      ^~
race.cpp:52:22: error: 'max_dp' was not declared in this scope
   52 |             maximize(max_dp[l][r][k], max_dp[r][to[k][l]][k ^ 1] + 1);  //case go back but not cut [l...r - 1]
      |                      ^~~~~~
race.cpp:52:49: error: 'to' was not declared in this scope
   52 |             maximize(max_dp[l][r][k], max_dp[r][to[k][l]][k ^ 1] + 1);  //case go back but not cut [l...r - 1]
      |                                                 ^~
race.cpp:55:23: error: 'to' was not declared in this scope
   55 |         for(int nxt = to[k][l]; nxt != r; nxt = to[k][nxt]){
      |                       ^~
race.cpp:56:16: error: 'e' was not declared in this scope
   56 |             if(e[l][nxt]){
      |                ^
race.cpp:57:26: error: 'dp' was not declared in this scope
   57 |                 maximize(dp[l][r][k], dp[l][nxt][k] + dp[nxt][r][k]);
      |                          ^~
race.cpp:58:26: error: 'max_dp' was not declared in this scope
   58 |                 maximize(max_dp[l][r][k], dp[l][nxt][k] + max_dp[nxt][r][k]);
      |                          ^~~~~~
race.cpp:62:18: error: 'max_dp' was not declared in this scope
   62 |         maximize(max_dp[l][r][k], max_dp[l][to[k ^ 1][r]][k]);
      |                  ^~~~~~
race.cpp:62:45: error: 'to' was not declared in this scope
   62 |         maximize(max_dp[l][r][k], max_dp[l][to[k ^ 1][r]][k]);
      |                                             ^~
race.cpp: In function 'int main()':
race.cpp:72:5: error: 'pair' was not declared in this scope
   72 |     pair<int, int> res = {0, 0};
      |     ^~~~
race.cpp:72:10: error: expected primary-expression before 'int'
   72 |     pair<int, int> res = {0, 0};
      |          ^~~
race.cpp:76:26: error: 'res' was not declared in this scope
   76 |                 maximize(res, make_pair(max_dp[i][j][k], i));
      |                          ^~~
race.cpp:76:41: error: 'max_dp' was not declared in this scope
   76 |                 maximize(res, make_pair(max_dp[i][j][k], i));
      |                                         ^~~~~~
race.cpp:76:31: error: 'make_pair' was not declared in this scope
   76 |                 maximize(res, make_pair(max_dp[i][j][k], i));
      |                               ^~~~~~~~~
race.cpp:82:9: error: 'cout' was not declared in this scope
   82 |         cout << res.first << ' ' << res.second + 1 << '\n';
      |         ^~~~
race.cpp:82:17: error: 'res' was not declared in this scope
   82 |         cout << res.first << ' ' << res.second + 1 << '\n';
      |                 ^~~
race.cpp:89:20: error: 'dp' was not declared in this scope
   89 |                 if(dp[i][j][k] <= 0) continue;
      |                    ^~
race.cpp:91:29: error: 'to' was not declared in this scope
   91 |                 int bestS = to[k][j];
      |                             ^~
race.cpp:92:38: error: 'e' was not declared in this scope
   92 |                 while(bestS != i && !e[bestS][i]) bestS = to[k][bestS];
      |                                      ^
race.cpp:99:24: error: 'e' was not declared in this scope
   99 |                     if(e[j][candidate]){ //S -> i -> ... -> j -> T -> ...
      |                        ^
race.cpp:100:40: error: 'max_dp' was not declared in this scope
  100 |                         int last = max(max_dp[to[k][bestS]][candidate][k ^ 1], max_dp[candidate][to[k ^ 1][i]][k]); //some last paths
      |                                        ^~~~~~
race.cpp:100:36: error: 'max' was not declared in this scope
  100 |                         int last = max(max_dp[to[k][bestS]][candidate][k ^ 1], max_dp[candidate][to[k ^ 1][i]][k]); //some last paths
      |                                    ^~~
race.cpp:101:44: error: 'dp' was not declared in this scope
  101 |                         int solution = 1 + dp[i][j][k] + 1 + last;
      |                                            ^~
race.cpp:102:25: error: 'cout' was not declared in this scope
  102 |                         cout << bestS << ' ' << i << ' ' << j << ' ' << candidate << '\n';
      |                         ^~~~
race.cpp:110:34: error: 'res' was not declared in this scope
  110 |                         maximize(res, {solution, bestS});
      |                                  ^~~
race.cpp:117:5: error: 'cout' was not declared in this scope
  117 |     cout << res.first << ' ' << res.second + 1 << '\n';
      |     ^~~~
race.cpp:117:13: error: 'res' was not declared in this scope
  117 |     cout << res.first << ' ' << res.second + 1 << '\n';
      |             ^~~
race.cpp:32:15: warning: unused variable 'inf' [-Wunused-variable]
   32 |     const int inf = 1e9;
      |               ^~~