Submission #1322676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1322676		NgTrung2217	Sailing Race (CEOI12_race)	C++20	100 / 100	757 ms	4640 KiB

race

#include <bits/stdc++.h>
#define task ""
#define ff first
#define ss second
using namespace std;
using ld = long double;
using ull = unsigned long long;
using ll = long long;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
const char el = '\n';
const char sp = ' ';
const ll inf = 1e9; //1e18;
const int maxN = 505;

int n, type;
bool edge[maxN][maxN];
int dp[maxN][maxN][2], dp1[maxN][maxN][2], nx[maxN][2];

void solve(int l, int r, int x)
{
    if (edge[l][r])
    {
        dp[l][r][x] = 1;
        dp1[l][r][x] = 1 + dp1[r][nx[l][x]][x ^ 1];
    }
    else
    {
        dp[l][r][x] = dp1[l][r][x] = -maxN;
    }
    for (int m = nx[l][x];m != r;m = nx[m][x])
    {
        dp[l][r][x] = max(dp[l][r][x], dp[l][m][x] + dp[m][r][x]);
        dp1[l][r][x] = max(dp1[l][r][x], dp[l][m][x] + dp1[m][r][x]);
    }
    dp1[l][r][x] = max(dp1[l][r][x], dp1[l][nx[r][x ^ 1]][x]);
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    if (!(cin >> n >> type)) return 0;
    for (int i = 0;i < n;++i)
    {
        int x;
        while (cin >> x && x != 0)
        {
            --x;
            edge[i][x] = 1;
        }
        nx[i][0] = (i + 1) % n;
        nx[i][1] = (i + n - 1) % n;
    }
    for (int d = 1;d < n;++d)
    {
        for (int l = 0;l < n;++l)
        {
            int r = (l + d) % n;
            solve(l, r, 0);
            solve(r, l, 1);
        }
    }
    pii ans = {-1, 0};
    for (int l = 0;l < n;++l)
    {
        for (int r = 0;r < n;++r)
        {
            for (int x = 0;x < 2;++x)
            {
                ans = max(ans, {dp1[l][r][x], l + 1});
            }
        }
    }
    if (type)
    {
        for (int l = 0;l < n;++l)
        {
            for (int r = 0;r < n;++r)
            {
                for (int x = 0;x < 2;++x)
                {
                    if (dp[l][r][x] <= 0) continue;
                    int st = nx[r][x];
                    while (st != l && !edge[st][l]) st = nx[st][x];
                    if (st == l) continue;
                    for (int ed = nx[st][x];ed != l;ed = nx[ed][x])
                    {
                        if (edge[r][ed])
                        {
                            int curAdd = max(dp1[ed][nx[st][x]][x ^ 1], dp1[ed][nx[l][x ^ 1]][x]);
                            ans = max(ans, {1 + dp[l][r][x] + 1 + curAdd, st + 1});
                        }
                    }
                }
            }
        }
    }
    cout << ans.ff << el << ans.ss << el;
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:45:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:46:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100