Submission #1091476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091476		ZeroCool	Sailing Race (CEOI12_race)	C++14	40 / 100	963 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 = 0;
        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 = x;
                            }
                        }
                    }
                }
            }
        }
        cout<<ans<<" "<<mi + 1<<'\n';
    }  
     
     
    //! MI SE SPIEEEEE!

• Subtask 1: 40 / 100