제출 #670031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
670031		kirakaminski968	Sailing Race (CEOI12_race)	C++17	100 / 100	1004 ms	4696 KiB

race

#include <bits/stdc++.h>
// #pragma GCC optimize("O3, unroll-loops")
// #pragma GCC target("avx2")
// #define int long long
using namespace std;
 
#define _upgrade                  \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define LINE "---------------------\n"
#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define Q queue
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define lb lower_bound 
#define ub upper_bound 
#define ub upper_bound 
#define sz(x) (int)x.size()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
using db = double;
using ld = long double;
using sint = short int;
using ll = long long;
using uint = unsigned int;
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VVVB = vector<VVB>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using PII = pair<int, int>;
using VPI = vector<PII>;
using VVPI = vector<VPI>;
using PLL = pair<ll, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int strToInt(string&a) {
    stringstream x(a);
    int b;
    x >> b;
    return b;
}
int gcd(int a, int b) {
   if (b == 0) return a;
   return gcd(b, a % b);
}
const db PI = acos(-1.0); //M_PI;
const ll INFF = 4e18;
const int INF = 1.07e9;
const int MOD = 1e9 + 7;
const int MOD1 = 998244353; //7*19*2^23 +1;
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int N = 500 + 5;
const int M = 2e5 + 5;
int nums[N];
int n, m, k, q, type;
string s;
bool edge[N][N];
int dp[N][N][2]; 
int dp1[N][N][2];
int nx[N][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] = -N;
    }
    for (int m = nx[l][x]; m != r; m=nx[m][x]) {
        chmax(dp[l][r][x], dp[l][m][x]+dp[m][r][x]);
        chmax(dp1[l][r][x], dp[l][m][x]+dp1[m][r][x]);
    }
    chmax(dp1[l][r][x], dp1[l][nx[r][x^1]][x]);
}
void go () {
    cin >> n >> type;
    for (int i = 0, x; i < n; i++) {
        while(cin >> x && x-- != 0) 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, r = (l+d)%n; l < n; l++, r=nx[r][0]) {
        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++) {
        chmax(ans, mp(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]);
                    chmax(ans, mp(1 + dp[l][r][x] + 1 + curAdd, st+1));
                }
            }
        }
    }
    cout << ans.ff << '\n' << ans.ss << '\n';
}
signed main () {
    _upgrade
    int T = 1;
    while(T--) go();
    return (0-0); 
}

• Subtask 1: 100 / 100