Submission #1091483

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091483	2024-09-21T00:40:19 Z	ZeroCool	Sailing Race (CEOI12_race)	C++14	40 / 100	977 ms	7004 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5976 KB	Output is correct
2	Incorrect	2 ms	5980 KB	Output isn't correct
3	Incorrect	2 ms	5980 KB	Output isn't correct
4	Incorrect	3 ms	5980 KB	Output isn't correct
5	Correct	3 ms	5980 KB	Output is correct
6	Incorrect	4 ms	6108 KB	Output isn't correct
7	Correct	5 ms	6116 KB	Output is correct
8	Incorrect	6 ms	6188 KB	Output isn't correct
9	Correct	7 ms	6224 KB	Output is correct
10	Correct	10 ms	6316 KB	Output is correct
11	Correct	9 ms	6124 KB	Output is correct
12	Incorrect	59 ms	6120 KB	Output isn't correct
13	Incorrect	159 ms	6232 KB	Output isn't correct
14	Correct	249 ms	6492 KB	Output is correct
15	Incorrect	809 ms	6744 KB	Output isn't correct
16	Incorrect	902 ms	7004 KB	Output isn't correct
17	Incorrect	808 ms	6748 KB	Output isn't correct
18	Correct	414 ms	6488 KB	Output is correct
19	Incorrect	964 ms	7004 KB	Output isn't correct
20	Incorrect	977 ms	7004 KB	Output isn't correct