Submission #1091485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091485		ZeroCool	Sailing Race (CEOI12_race)	C++14	40 / 100	978 ms	7256 KiB

race

#include <bits/stdc++.h>
using namespace std;
    
#define int long long
#define ll long long
#define ar array
    
const int INF = 1e17;
const int N = 600;
const int Q = 105;
const int MOD = 1e9 + 7;
const int LOG = 60;
    
int dp[N][N][2];
int n;
bool g[N][N];
    
int f(int l,int r,bool d){
    if(dp[l][r][d] != -1)return dp[l][r][d];
    int ans = 0;
    
    for(int i = (l + 1) % n;i != r;i = (i + 1) % n){
        int prv = d ? r : l; 
        if(g[prv][i]){
            ans = max(ans, f(l, i, 1) + 1);
            ans = max(ans, f(i,r, 0) + 1);
        }
    }
    
    return dp[l][r][d] = ans;
}
    
bool in(int l, int x ,int r){
    if(l > r)r += n;
    if(l > x)x += n;
    return l < x && x < r;
}
    
int dist[N][2], harb[N][2];
    
vector<int> G[N];
    
signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin>>n;
    int garb;
    cin>>garb;
    for(int i = 0;i < n;i++){
        int x;
        cin>>x;
        while(x){
            g[i][x - 1] = 1;
            G[i].push_back(x - 1);
            cin>>x;
        }
    }
    
    int ans = -1;
    int mi = - 1;
    if(garb == 0){
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                if(!g[i][j])continue;
                int res = f(i, j, 1) + 1;
                if(res > ans){  
                    ans = res;
                    mi = i;
                }
                res = f(j, i, 0) + 1;
                if(res > ans){
                    ans = res;
                    mi = i;
                }
            }
        }
        cout<<ans<<" "<<mi + 1<<'\n';
        return 0;
    }
    
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            for(int k = 0;k < 2;k++){
                dist[j][k] = -INF;
                harb[j][k] = -1;
            }
        }
        for(auto d: {-1, 1}){
            int t = (d == 1);
            dist[i][t] = 0;
            for(int x = (i + d + n) % n;x != i; x = (x + d + n) % n){
                for(auto u: G[x]){
                    dist[x][t] = max(dist[x][t], dist[u][t] + 1);
                    if(harb[u][t] == -1)harb[u][t] = x;
                }
            }
        }
        for(auto j : G[i]){
            for(auto d: {-1, 1}){
                int t = (d == 1);
                for(int x = (i + d + n) % n;x != j; x = (x + d + n) % n){
                    int dx = dist[x][t];
                    int y = harb[x][!t];
                    if(y == -1)continue;
                    if(in(i, x, j) ^ in(i, y, j)){
                        int ans1 = 2 + dx;
                        if(in(i, y, j))ans1 += f(y, j, 1);    
                        else ans1 += f(j, y, 0);   
                        if(ans1 > ans){
                            ans = ans1;
                            mi = y;
                        }
                        int ans2 = 2 +  dx;
                        if(in(i, x, j))ans2 += f(x, j, 1);
                        else ans2 += f(j, x, 0);
                        if(ans2 > ans){
                            ans = ans2;
                            mi = y;
                        }
                    }
                }
            }
        }
    }
    cout<<ans<<" "<<mi + 1<<'\n';
}  
    
    
//! MI SE SPIEEEEE!

• Subtask 1: 40 / 100