Submission #1041882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041882		jhinezeal123	Sailing Race (CEOI12_race)	C++17	85 / 100	622 ms	9308 KiB

race

#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
#define show(T) {for (auto x:T) cout<<x<<' ';cout<<endl;}
#define all(T) T.begin(),T.end()
using namespace std;
const double eps = 0.0000001;
const int mod = 1e9+7;
const int N = 505;
const int MATRIX_SIZE = 64;
const int BLOCK=500;
int n,dp1[N][N][2],dp2[N][N][2],k;
bool ke[N][N];
vector <int> G[N];
int id(int x){
    if (x>n) x-=n;
    else if (x<1) x+=n;
    return x;
}
void tim_dp1(){
    for (int i=1,mid1,to1,mid2,to2;i<=n;++i){
        for (int j=1;j<n;++j){
            to1=id(i+j);
            to2=id(i-j);
            for (int z=1;z<j;++z){
                mid1=id(i+z);
                mid2=id(i-z);
                if (ke[mid1][to1]&&dp1[i][mid1][0]) 
                    dp1[i][to1][0]=max(dp1[i][to1][0],dp1[i][mid1][0]+1);
                if (ke[mid2][to2]&&dp1[i][mid2][1])
                    dp1[i][to2][1]=max(dp1[i][to2][1],dp1[i][mid2][1]+1);
            }
        }
    }
}
void tim_dp2(){
    for (int kc=1;kc<n;++kc){
        for (int i=1,j1,j2,mid1,mid2;i<=n;++i){
            j1=id(i+kc);
            j2=id(i-kc);
            dp2[i][j1][0]=max(dp1[i][j1][0],dp2[i][id(i+kc-1)][0]);
            dp2[i][j2][1]=max(dp1[i][j2][1],dp2[i][id(i-kc+1)][1]);
            for (int z=1;z<kc;++z){
                mid1=id(i+z);
                mid2=id(i-z);
                if (dp1[i][mid1][0])
                    dp2[i][j1][0]=max(dp2[i][j1][0],dp1[i][mid1][0]+dp2[mid1][j1][0]);
                if (dp1[i][mid2][1])
                    dp2[i][j2][1]=max(dp2[i][j2][1],dp1[i][mid2][1]+dp2[mid2][j2][1]);
            }
            if (ke[i][j1]) dp2[i][j1][0]=max(dp2[i][j1][0],dp2[j1][id(i+1)][1]+1);
            if (ke[i][j2]) dp2[i][j2][1]=max(dp2[i][j2][1],dp2[j2][id(i-1)][0]+1);
        }
    }
}
void solve(){
    cin>>n>>k;
    for (int i=1,tam;i<=n;++i){
        // getline(cin,trol);
        // trol+=' ';
        // for (auto x:trol){
        //     if (x==' '){
        //         G[i].push_back(cur);
        //         // cout<<i<<' '<<cur<<endl;
        //         ke[i][cur]=true;
        //         dp1[i][cur][0]=dp1[i][cur][1]=1;
        //         cur=0;
        //     }
        //     else cur=cur*10+(x-'0');
        // }
        cin>>tam;
        while (tam){
            G[i].push_back(tam);
            ke[i][tam]=true;
            dp1[i][tam][0]=dp1[i][tam][1]=1;
            cin>>tam;
        }
    }
    tim_dp1();
    tim_dp2();
    ii ans={0,0};
    if (!k){
        for (int i=1;i<=n;++i){
            for (auto x:G[i]){
                ans=max({ans,ii(dp2[x][id(i-1)][0]+1,i),ii(dp2[x][id(i+1)][1]+1,i)});
            }
        }
        cout<<ans.fi<<endl<<ans.se;
        return;
    }
    for (int i=1,mid;i<=n;++i){
        for (int j=1;j<=n;++j){
            if (dp1[j][i][0]){
                mid=0;
                for (int z=1,tam;z<n;++z){
                    tam=id(i+z);
                    if (tam==j) break;
                    if (ke[tam][j]) {
                        mid=tam;
                        break;
                    }
                }
                if (!mid) continue;
                for (int z=1,tam;z<n;++z){
                    tam=id(mid+z);
                    if (tam==j) break;
                    if (!ke[i][tam]) continue;
                    ans=max(ans,ii(max(dp2[tam][id(mid+1)][1],dp2[tam][id(j-1)][0])+dp1[j][i][0]+2,mid));
                }
            }
            if (dp1[j][i][1]){
                mid=0;
                for (int z=1,tam;z<n;++z){
                    tam=id(i-z);
                    if (tam==j) break;
                    if (ke[tam][j]){
                        mid=tam;
                        break;
                    }
                }
                if (!mid) continue;
                for (int z=1,tam;z<n;++z){
                    tam=id(mid-z);
                    if (tam==j) break;
                    if (!ke[i][tam]) continue;
                    ans=max(ans,ii(max(dp2[tam][id(mid-1)][0],dp2[tam][id(j+1)][1])+dp1[j][i][1]+2,mid));
                }
            }
        }
    }
    cout<<ans.fi<<endl<<ans.se;
}
main() {
    //freopen("ok.inp","r",stdin);
   // freopen("ok.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    // cout<<endl<<clock()/1000.0;
}

Compilation message (stderr)

race.cpp:138:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  138 | main() {
      | ^~~~

• Subtask 1: 85 / 100