Submission #1106763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106763		Icelast	Sailing Race (CEOI12_race)	C++17	40 / 100	508 ms	4776 KiB

race

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void solve(){
    int n, k;
    cin >> n >> k;
    vector<vector<int>> adj(n+1);
    vector<vector<bool>> mat(n+1, vector<bool>(n+1, false));
    for(int i = 1; i <= n; i++){
        while(true){
            int x;
            cin >> x;
            if(x == 0) break;
            adj[i].push_back(x);
            mat[i][x] = true;
        }
    }
    vector<vector<int>> f(n+1, vector<int>(n+1, 0)), g(n+1, vector<int>(n+1, 0)), mf(n+1, vector<int>(n+1, 0)), mg(n+1, vector<int>(n+1, 0));
    //f is counter clockwise, g is clockwise such that path in region [i, j] start point is i, end point arbitrary
    //mf is counter clockwise, mg is clockwise such that path in region [i, j], start point is i, end point is j
    for(int i = 1; i <= n; i++){
        for(int j : adj[i]){
            f[i][j] = 1;
            g[i][j] = 1;
            mf[i][j] = 1;
            mg[i][j] = 1;
        }
    }
    auto chmax = [&](int &a, int b) -> void{
        a = max(a, b);
    };
    for(int len = 2; len < n; len++){
        for(int i = 1; i <= n; i++){
            int j = i+len;
            if(j > n) j-=n;
            int k;
            int nxt_i = i+1, prv_i = i-1;
            if(nxt_i > n) nxt_i-=n;
            if(prv_i == 0) prv_i+=n;
            for(k = i; ; k++){
                if(k == n+1){
                    k = 1;
                }else if(k == 0){
                    k = n;
                }

                if(mat[i][k] == 1) chmax(f[i][j], mat[i][k]+max(f[k][j], g[k][nxt_i]));
                chmax(mf[i][j], mf[i][k] + mf[k][j]);
                if(k == j) break;
            }
            j = i-len;
            if(j < 1) j+=n;
            for(k = i; ; k--){
                if(k == n+1){
                    k = 1;
                }else if(k == 0){
                    k = n;
                }
                if(mat[i][k] == 1) chmax(g[i][j], mat[i][k]+max(g[k][j], f[k][prv_i]));
                chmax(mg[i][j], mg[i][k] + mg[k][j]);
                if(k == j) break;
            }
        }
    }
    if(k == 0){
        int ans = -1, ansi = -1;
        for(int i = 1; i <= n; i++){
            int j = i-1;
            if(j == 0) j+=n;
            if(ans < f[i][j]){
                ans = f[i][j];
                ansi = i;
            }
            j = i+1;
            if(j == n+1) j-=n;
            if(ans < g[i][j]){
                ans = g[i][j];
                ansi = i;
            }
        }
        cout << ans << "\n" << ansi;
        return;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("main.inp", "r", stdin);
    //freopen("main.out", "w", stdout);
    solve();
}

• Subtask 1: 40 / 100