Submission #1091484

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091484	2024-09-21T00:47:51 Z	ZeroCool	Sailing Race (CEOI12_race)	C++14	40 / 100	1033 ms	7080 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 = y;
                        }
                    }
                }
            }
        }
    }
    cout<<ans<<" "<<mi + 1<<'\n';
}  
    
    
//! MI SE SPIEEEEE!

Subtask #1

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5976 KB	Output is correct
2	Incorrect	3 ms	5980 KB	Output isn't correct
3	Incorrect	3 ms	5980 KB	Output isn't correct
4	Incorrect	4 ms	5980 KB	Output isn't correct
5	Correct	3 ms	5980 KB	Output is correct
6	Incorrect	4 ms	5980 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	8 ms	5980 KB	Output is correct
10	Correct	9 ms	6312 KB	Output is correct
11	Correct	9 ms	6236 KB	Output is correct
12	Incorrect	62 ms	6236 KB	Output isn't correct
13	Incorrect	159 ms	6392 KB	Output isn't correct
14	Correct	248 ms	6492 KB	Output is correct
15	Incorrect	872 ms	6804 KB	Output isn't correct
16	Incorrect	893 ms	7000 KB	Output isn't correct
17	Incorrect	806 ms	6744 KB	Output isn't correct
18	Correct	428 ms	6488 KB	Output is correct
19	Incorrect	1012 ms	7080 KB	Output isn't correct
20	Incorrect	1033 ms	7080 KB	Output isn't correct