답안 #537813

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537813 2022-03-15T15:18:42 Z MinhAnhnd Sailing Race (CEOI12_race) C++14
0 / 100
144 ms 65536 KB
#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;
      |           ^
# 결과 실행 시간 메모리 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