Submission #840053

#	Time	Username	Problem	Language	Result	Execution time	Memory
840053		angelo_torres	Longest Trip (IOI23_longesttrip)	C++17	25 / 100	990 ms	276 KiB

longesttrip

#include "longesttrip.h"
#define sz(v) (int) v.size()
#define ff first
#define ss second

using namespace std;
typedef pair<int,int> ii;

vector<int> longest_trip(int N, int D)
{
    vector<vector<bool>> A(N);
    for(int i = 0; i < N; ++i) A[i].resize(N);
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < i; ++j){
            A[i][j] = are_connected({i},{j});
            A[j][i] = A[i][j];
        }
    }
    vector<int> G(N);
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j) if(A[i][j]) G[i]++;
    }
    int x = 0;
    for(int i = 1; i < N; ++i){
        if(G[i] < G[x]) x = i;
    }
    vector<int> ans;
    if(G[x] <= (N/2)-1){
        for(int i = 0; i < N; ++i){
            if((i == x) || A[x][i]) continue;
            ans.push_back(i);
        }
        return ans;
    }
    // G[x] >= (N/2) -> G[i] >= (N/2) for all 0 <= i < N
    vector<bool> T(N,false);
    ans = {0};
    T[0] = 1;
    int last = 0;
    for(int i = 1; i < (N+1)/2; ++i){
        for(int j = 0; j < N; ++j){
            if(T[j] || !A[last][j] || (j == last)) continue;
            // j is not in ans, j is adjacent to last, j is not last
            ans.push_back(j); 
            last = j;
            T[j] = 1;
            break;
        }
    }
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 60