Submission #537808

#	Time	Username	Problem	Language	Result	Execution time	Memory
537808		MinhAnhnd	Sailing Race (CEOI12_race)	C++14	0 / 100	46 ms	65536 KiB

race

#include <bits/stdc++.h>
#include <iostream>
#define ll long long
#define ull unsigned ll
using namespace std;


bool branches[501][501]={};
bool chaychua[501][501][2]={};
vector<long> from[501];
long N,K;
long dp[501][501][2]={};
deque<long> dp1[501][501][2];
long depth = -1;

long pre(long p){
    if (p == 1) return N;
    return p-1;
}
long nex(long p){
    if (p == N) return 0;
    return p+1;
}

deque<long> join(deque<long>a, deque<long>b){
    deque<long> ans;
    auto i = a.begin();
    auto j = b.begin();
    while(i!=a.end()&&j!=b.end()){
        auto moi= *i;
        auto hai= *j;
        if (moi < hai){
            i++;
            continue;
        }
        if (hai < moi){
            j++;
            continue;
        }
        ans.push_back(moi);
        if (hai <= moi){
            j++;
        }
        else {
            i++;
        }
    }
    return ans;
}
long memo(long start, long end,long direction){
    if (chaychua[start][end][direction]) return dp[start][end][direction];
    chaychua[start][end][direction] = 1;


    //counter-clockwise;

    for(long i = nex(start);i != end; i = nex(i)){
        if (branches[direction?end:start][i]){
            long alpha = memo(i,end,0);
            long beta = memo(start,i,1);
            dp[start][end][direction] = max(dp[start][end][0],max(alpha,beta))+1;

        }
    }

    for(long i = nex(start);i != end; i = nex(i)){
        if (branches[direction?end:start][i] && (max(dp[i][end][0],dp[start][i][1])+1)==dp[start][end][direction]){
            long beta = dp[start][i][1];
            long alpha = dp[i][end][0];


            //auto left = dp1[start][i][1];
            //auto right = dp1[i][end][0];
            deque<long> ans;

            if (alpha > beta){
                    ans = dp1[i][end][0];
                    ans.push_front(i);

            }

            else if (alpha < beta){
                    ans = dp1[start][i][1];
                    ans.push_back(i);
            }
            else{
                    ans.push_back(i);
            }

                if (dp1[start][end][direction].empty()){
                    dp1[start][end][direction] = ans;
                }
                else{
                    dp1[start][end][direction] = join(dp1[start][end][0],ans);
                }
        }
    }





    return dp[start][end][direction];
}

int main(){
    cin>>N>>K;
    long v,u=0;

    for(long i = 1;i<=N;i++){
        cin>>v;
        while(v!=0){
            from[v].push_back(i);
            branches[i][v]=1;
            cin>>v;

        }
    }
    long maxi = -1;
    long mem = 0;

    if (K == 0){
    for(long i = 1;i<=N;i++){
        //counter-clockwise
        long val = memo(i,i,0);
        if(val>=maxi){
            maxi = val;
            mem = i;
        }

    }

    cout<<maxi<<endl<<mem<<endl;
    return 0;
    }

    for(long i = 1;i<=N;i++){
        //counter-clockwise
        long val = memo(i,i,0);
        if(val>=maxi){
            maxi = val;
            mem = i;
            for(auto u:from[i]){
                auto t = lower_bound(dp1[i][i][0].begin(),dp1[i][i][0].end(),u);
                if (t == dp1[i][i][0].end()){
                    continue;
                }
                if ((*t) != u){
                    continue;
                }
                maxi = val+1;
                mem = u;
                break;
            }
        }
    }

    cout<<maxi<<endl<<mem<<endl;
}

Compilation message (stderr)

race.cpp: In function 'int main()':
race.cpp:108:12: warning: unused variable 'u' [-Wunused-variable]
  108 |     long v,u=0;
      |            ^

• Subtask 1: 0 / 100