제출 #1219265

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

longesttrip

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

typedef long long 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;
            for(ll j=0; j<n; j++){
                if(i!=j && !adj[i][j]) ans.push_back(j);
            }
            return ans;
        }
    }

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

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