Submission #603841

#	Time	Username	Problem	Language	Result	Execution time	Memory
603841		Mazaalai	Sailing Race (CEOI12_race)	C++17	20 / 100	410 ms	2552 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;
// PQ going up <int, VI, greater<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;
vector <int> paths[N];
bool edge[N][N];
int dp[N][N][2];
bool mid (int l, int r, int m) {
    if (l < r) return (l < m && m < r);
    return (
        (l < m && m < n) || 
        (l > m && m < r)
    );
}
int f (int a) {
    return (a+1)%n;
}
void go () {
    cin >> n >> type;
    for (int i = 0, x; i < n; i++) {
        while(cin >> x && x != 0) {
            // paths[i].pb(x);
            edge[i][x-1] = 1;
        }
    }
    PII ans = {-1, 0};
    for (int d = 2; d < n; d++)
    for (int l = 0, r = (l+d>=n?l+d-n:l+d); l < n ; l++, r=(r+1>=n?0:r+1)) {
        for (int m = (l+1>=n?0:l+1); m != r; m=(m+1>=n?0:m+1)) {
            if (edge[l][m]) {
                chmax(dp[l][r][0], dp[l][m][1]+1);
                chmax(dp[l][r][0], dp[m][r][0]+1);
            }
            if (edge[r][m]) {
                chmax(dp[l][r][1], dp[l][m][1]+1);
                chmax(dp[l][r][1], dp[m][r][0]+1);
            }
        }
        // chmax(ans, mp(dp[l][r][0], l));
        // chmax(ans, mp(dp[l][r][1], r));
    }
    for (int l = 0; l < n; l++)
    for (int r = 0; r < n; r++) {
        if (l == r) continue;
        if (edge[l][r]) {
            int v = max(dp[l][r][0], dp[r][l][1]);
            if (v >= ans.ff) ans = {v, l};
        }
    }
    cout << ans.ff+1 << '\n' << ans.ss+1 << '\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); //<3
}

/* stuff you should look for
    * int overflow, array bounds
    * special cases (n=1?)
    
*/

• Subtask 1: 20 / 100