Submission #1091476

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091476	2024-09-21T00:06:39 Z	ZeroCool	Sailing Race (CEOI12_race)	C++14	40 / 100	963 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 = 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	5980 KB	Output is correct
2	Incorrect	2 ms	5980 KB	Output isn't correct
3	Incorrect	3 ms	5976 KB	Output isn't correct
4	Incorrect	3 ms	5976 KB	Output isn't correct
5	Correct	3 ms	6124 KB	Output is correct
6	Incorrect	4 ms	5976 KB	Output isn't correct
7	Correct	5 ms	5976 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	9 ms	6236 KB	Output is correct
11	Correct	9 ms	6248 KB	Output is correct
12	Incorrect	61 ms	6236 KB	Output isn't correct
13	Incorrect	163 ms	6396 KB	Output isn't correct
14	Correct	247 ms	6472 KB	Output is correct
15	Incorrect	799 ms	6800 KB	Output isn't correct
16	Incorrect	906 ms	7256 KB	Output isn't correct
17	Incorrect	816 ms	6800 KB	Output isn't correct
18	Correct	413 ms	6548 KB	Output is correct
19	Incorrect	961 ms	7000 KB	Output isn't correct
20	Incorrect	963 ms	7004 KB	Output isn't correct