Submission #1091298

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091298	2024-09-20T12:50:35 Z	vjudge1	Sailing Race (CEOI12_race)	C++17	40 / 100	986 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))ans1 += f(x, j, 1);
                        else ans1 += 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	3 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	4 ms	5976 KB	Output is correct
6	Incorrect	5 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	7 ms	6204 KB	Output is correct
10	Correct	9 ms	6312 KB	Output is correct
11	Correct	9 ms	6236 KB	Output is correct
12	Incorrect	60 ms	6236 KB	Output isn't correct
13	Incorrect	157 ms	6236 KB	Output isn't correct
14	Correct	252 ms	6492 KB	Output is correct
15	Incorrect	804 ms	6808 KB	Output isn't correct
16	Incorrect	906 ms	7000 KB	Output isn't correct
17	Incorrect	804 ms	6744 KB	Output isn't correct
18	Correct	415 ms	6544 KB	Output is correct
19	Incorrect	985 ms	7080 KB	Output isn't correct
20	Incorrect	986 ms	7004 KB	Output isn't correct