제출 #646240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646240		new_acc	Sailing Race (CEOI12_race)	C++14	70 / 100	1836 ms	4732 KiB

race

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e2+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
int n,dp[N][N][2],nxt[N],dp2[N][N][2],nw[N],nn[N];
bool kr[N][N];
void solve(){
    int xd;
    cin>>n>>xd;
    for(int a,i=1;i<=n;i++){
        cin>>a;
        while(a!=0){
            if(a!=i) kr[i][a]=1;
            cin>>a;
        }
    }
    if(n==1){
        cout<<1<<"\n";
        return;
    }
    for(int i=1;i<n;i++) nxt[i]=i+1;
    nxt[n]=1;
    for(int dl=1;dl<n;dl++){
        for(int i=1;i<=n;i++){
            int v=i,kon=i+dl;
            if(kon>n) kon-=n;
            for(int i2=0;i2<=dl;i2++,v=nxt[v]){
                if(kr[i][v]){
                    dp[i][dl][0]=max({dp[i][dl][0],dp[v][dl-i2][0]+1,
                            dp[nxt[i]][i2-1][1]+1});
                }
                if(kr[kon][v]){
                    dp[i][dl][1]=max({dp[i][dl][1],dp[i][i2][1]+1,
                            dp[v][dl-i2-1][0]+1});
                }
            }
        }
    }
    int res=0,g=0;
    for(int i=1;i<=n;i++){
        res=max(res,dp[i][n-1][0]);
        if(dp[i][n-1][0]==res) g=i;
    }
    if(xd==0){
        cout<<res<<"\n"<<g<<"\n";
    }else{
        for(int dl=1;dl<n;dl++){
            for(int i=1;i<=n;i++){
                int v=i,kon=i+dl;
                if(kon>n) kon-=n;
                dp2[i][dl][0]=-INFi;
                dp2[i][dl][1]=-INFi;
                for(int i2=0;i2<=dl;i2++,v=nxt[v]){
                    if(kr[i][v]){
                        dp2[i][dl][0]=max(dp2[i][dl][0],dp2[v][dl-i2][0]+1);
                    }
                    if(kr[kon][v]){
                        dp2[i][dl][1]=max(dp2[i][dl][1],dp2[i][i2][1]+1);
                    }
                }
            }
        }
        for(int s=1;s<=n;s++){
            for(int i2=1;i2<=n;i2++) nw[i2]=INFi,nn[i2]=INFi;
            int v=nxt[s];
            for(int i2=1;i2<n;i2++,v=nxt[v]){
                for(int i3=1;i3<=n;i3++){
                    if(kr[i3][v]){
                        nw[i3]=(nw[i3]==INFi?i2:nw[i3]);
                        nn[i3]=v;
                    }
                }
                int pom=nxt[v],l=1;
                while(pom!=s){
                    int cnt=dp2[v][l][0]+1,dod=0;
                    if(nw[pom]!=INFi) dod=dp[nxt[s]][nw[pom]-1][1]+1;
                    if(nn[pom]!=INFi){
                        int g=nn[pom];
                        int odl=v-g;
                        if(odl<0) odl=v+n-g;
                        dod=max(dod,dp[g][odl-1][0]+1);
                    }
                    if(kr[s][v]){
                        res=max(res,cnt+dod);
                        if(cnt+dod==res){
                            g=s;
                        }
                    }
                    pom=nxt[pom],l++;
                }
            }
            for(int i2=1;i2<=n;i2++) nw[i2]=INFi,nn[i2]=INFi;
            v=s-1;
            for(int i2=1;i2<n;i2++,v--){
                if(v==0) v=n;
                for(int i3=1;i3<=n;i3++){
                    if(kr[i3][v]){
                        nn[i3]=(nn[i3]==INFi?v:nn[i3]);
                        nw[i3]=v;
                    }
                }
                int pom=nxt[s],l=1;
                while(pom!=v){
                    int cnt=dp2[pom][(n-i2)-l][1]+1,dod=0;
                    if(nw[pom]!=INFi){
                        int g=nw[pom];
                        int odl=s-g;
                        if(odl<0) odl=s+n-g;
                        dod=dp[g][odl-1][0]+1;
                    }
                    if(nn[pom]!=INFi){
                        int g=nn[pom];
                        int odl=g-v;
                        if(odl<0) odl=g+n-v;
                        dod=max(dod,dp[nxt[v]][odl-1][1]+1);
                    }
                    if(kr[s][v]){
                        res=max(res,cnt+dod);
                        if(cnt+dod==res){
                            g=s;
                        }
                    }
                    pom=nxt[pom],l++;
                }
            }
        }
        cout<<res<<"\n"<<g<<"\n";
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

• Subtask 1: 70 / 100