Submission #537813

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
537813	2022-03-15T15:18:42 Z	MinhAnhnd	Sailing Race (CEOI12_race)	C++14	0 / 100	144 ms	65536 KB

race

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


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

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

deque<int> join(deque<int>a, deque<int>b){
    deque<int> 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;
}
int memo(int start, int end,int direction){
    if (chaychua[start][end][direction]) return dp[start][end][direction];
    chaychua[start][end][direction] = 1;


    //counter-clockwise;

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

        }
    }

    for(int 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]){
            int beta = dp[start][i][1];
            int alpha = dp[i][end][0];


            //auto left = dp1[start][i][1];
            //auto right = dp1[i][end][0];
            deque<int> 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;
    int v,u=0;

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

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

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

    }

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

    for(int i = 1;i<=N;i++){
        //counter-clockwise
        int 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

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

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	35 ms	54704 KB	Memory limit exceeded
2	Runtime error	41 ms	54800 KB	Memory limit exceeded
3	Runtime error	43 ms	54860 KB	Memory limit exceeded
4	Runtime error	45 ms	55196 KB	Memory limit exceeded
5	Runtime error	43 ms	55480 KB	Memory limit exceeded
6	Runtime error	44 ms	55712 KB	Memory limit exceeded
7	Runtime error	47 ms	55652 KB	Memory limit exceeded
8	Runtime error	45 ms	56608 KB	Memory limit exceeded
9	Runtime error	55 ms	56396 KB	Memory limit exceeded
10	Runtime error	60 ms	57112 KB	Memory limit exceeded
11	Runtime error	66 ms	56676 KB	Memory limit exceeded
12	Runtime error	144 ms	63280 KB	Memory limit exceeded
13	Runtime error	83 ms	65536 KB	Execution killed with signal 11
14	Runtime error	81 ms	65536 KB	Execution killed with signal 11
15	Runtime error	88 ms	65536 KB	Execution killed with signal 11
16	Runtime error	110 ms	65536 KB	Execution killed with signal 11
17	Runtime error	90 ms	65536 KB	Execution killed with signal 11
18	Runtime error	81 ms	65536 KB	Execution killed with signal 11
19	Runtime error	90 ms	65536 KB	Execution killed with signal 11
20	Runtime error	94 ms	65536 KB	Execution killed with signal 11