제출 #646273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646273		new_acc	Sailing Race (CEOI12_race)	C++14	95 / 100	2497 ms	4756 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];
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<<0<<"\n"<<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;
            int v=nxt[s];
            for(int i2=1;i2<n;i2++,v=nxt[v]){
                int pom=nxt[v],li=1;
                while(pom!=s){
                    if(kr[s][v] and nw[pom]>=0){
                        res=max(res,nw[pom]+dp2[v][li][0]+2);
                        if(nw[pom]+dp2[v][li][0]+2==res){
                            g=s;
                        }
                    }
                    pom=nxt[pom],li++;
                }
                for(int i3=1;i3<=n;i3++){
                    if(kr[i3][v]){
                        nw[i3]=max(nw[i3],dp[nxt[s]][i2-1][1]);
                    }
                }
            }
            for(int i2=1;i2<=n;i2++) nw[i2]=-INFi;
            v=s-1;
            for(int i2=1;i2<n;i2++,v--){
                if(v==0) v=n;
                int pom=nxt[s],li=1;
                while(pom!=v){
                    int odl=n-i2;
                    if(kr[s][v] and nw[pom]>=0){
                        res=max(res,nw[pom]+dp2[pom][odl-li][1]+2);
                        if(nw[pom]+dp2[pom][odl-li][1]+2==res){
                            g=s;
                        }
                    }
                    pom=nxt[pom],li++;
                }
                for(int i3=1;i3<=n;i3++){
                    if(kr[i3][v]){
                        nw[i3]=max(nw[i3],dp[v][i2-1][0]);
                    }
                }
            }
        }
        for(int v=1;v<=n;v++){
            for(int i2=1;i2<=n;i2++) nw[i2]=-INFi;
            int s=nxt[v];
            for(int i2=1;i2<n;i2++,s=nxt[s]){
                int pom=nxt[s],li=1;
                while(pom!=v){
                    int odl=n-i2;
                    if(kr[s][v] and nw[pom]>=0){
                        res=max(res,nw[pom]+dp2[pom][odl-li][1]+2);
                        if(nw[pom]+dp2[pom][odl-li][1]+2==res){
                            g=s;
                        }
                    }
                    pom=nxt[pom],li++;
                }
                for(int i3=1;i3<=n;i3++){
                    if(kr[i3][s]){
                        nw[i3]=max(nw[i3],dp[nxt[v]][i2-1][1]);
                    }
                }
            }
            s=v-1;
            for(int i2=1;i2<=n;i2++) nw[i2]=-INFi;
            for(int i2=1;i2<n;i2++,s--){
                if(s==0) s=n;
                int pom=nxt[v],li=1;
                while(pom!=s){
                    if(kr[s][v] and nw[pom]>=0){
                        res=max(res,nw[pom]+dp2[v][li][0]+2);
                        if(nw[pom]+dp2[v][li][0]+2==res){
                            g=s;
                        }
                    }
                    pom=nxt[pom],li++;
                }
                for(int i3=1;i3<=n;i3++){
                    if(kr[i3][s]){
                        nw[i3]=max(nw[i3],dp[s][i2-1][0]);
                    }
                }
            }
        }
        cout<<res<<" "<<g<<"\n";
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

• Subtask 1: 95 / 100