Submission #1093470

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1093470	2024-09-26T23:51:17 Z	ArtistWall	Sailing Race (CEOI12_race)	C++17	100 / 100	961 ms	4832 KB

race

#include <bits/stdc++.h>
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);
 
 
 
 
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));
    }

    // type = 0;
    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 () {
 
#ifndef ONLINE_JUDGE
    // freopen("0.in", "r", stdin);
    // freopen("0.out", "w", stdout);
#endif
    _upgrade
    int T = 1;
    while(T--) go();
    return (0-0);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	860 KB	Output is correct
6	Correct	2 ms	860 KB	Output is correct
7	Correct	2 ms	860 KB	Output is correct
8	Correct	3 ms	1116 KB	Output is correct
9	Correct	3 ms	1252 KB	Output is correct
10	Correct	5 ms	1112 KB	Output is correct
11	Correct	4 ms	1116 KB	Output is correct
12	Correct	54 ms	2168 KB	Output is correct
13	Correct	161 ms	3004 KB	Output is correct
14	Correct	223 ms	3672 KB	Output is correct
15	Correct	844 ms	4768 KB	Output is correct
16	Correct	900 ms	4792 KB	Output is correct
17	Correct	869 ms	4700 KB	Output is correct
18	Correct	443 ms	4700 KB	Output is correct
19	Correct	951 ms	4696 KB	Output is correct
20	Correct	961 ms	4832 KB	Output is correct