제출 #1219262

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219262		mariza	가장 긴 여행 (IOI23_longesttrip)	C++17	25 / 100	332 ms	804 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

typedef int ll;

vector<int> longest_trip(int n, int D){
    vector<ll> g[n];
    bool adj[n][n]={};
    for(ll i=0; i<n; i++){
        for(ll j=i+1; j<n; j++){
            if(are_connected({(int)i},{(int)j})){
                g[i].push_back(j);
                g[j].push_back(i);
                adj[i][j]=1;
                adj[j][i]=1;
            }
        }
    }

    for(ll i=0; i<n; i++){
        if(g[i].size()+1<=n/2){
            // cout<<"! "<<i<<endl;
            vector<int> ans((n+1)/2,0);
            ll c=0;
            for(ll j=0; j<n && c<(n+1)/2; j++){
                if(i!=j && !adj[i][j]){
                    ans[c]=j;
                    c++;
                }
                // n/2;
            }
            return ans;
        }
    }

    vector<int> ans((n+1)/2,0);
    ans[0]=0;
    bool vis[n]={};
    for(ll i=1; i<(n+1)/2; i++){
        ll curr=ans[i-1];
        vis[curr]=1;
        for(auto nxt:g[curr]){
            if(!vis[nxt]){
                ans[i]=nxt;
                break;
            }
        }
    }
    return ans;
}

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