Submission #1091485

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091485	2024-09-21T00:49:21 Z	ZeroCool	Sailing Race (CEOI12_race)	C++14	40 / 100	978 ms	7256 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 = -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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5980 KB	Output is correct
2	Incorrect	2 ms	6008 KB	Output isn't correct
3	Incorrect	2 ms	6112 KB	Output isn't correct
4	Incorrect	3 ms	5980 KB	Output isn't correct
5	Correct	3 ms	5976 KB	Output is correct
6	Incorrect	5 ms	6176 KB	Output isn't correct
7	Correct	5 ms	5980 KB	Output is correct
8	Incorrect	6 ms	5980 KB	Output isn't correct
9	Correct	7 ms	5980 KB	Output is correct
10	Correct	11 ms	6232 KB	Output is correct
11	Correct	9 ms	6236 KB	Output is correct
12	Incorrect	59 ms	6312 KB	Output isn't correct
13	Incorrect	165 ms	6232 KB	Output isn't correct
14	Correct	251 ms	6488 KB	Output is correct
15	Incorrect	836 ms	6748 KB	Output isn't correct
16	Incorrect	906 ms	7256 KB	Output isn't correct
17	Incorrect	810 ms	6748 KB	Output isn't correct
18	Correct	413 ms	6492 KB	Output is correct
19	Incorrect	978 ms	7000 KB	Output isn't correct
20	Incorrect	978 ms	7004 KB	Output isn't correct