제출 #1233363

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

longesttrip

#include <vector>
#include <set>
#include "longesttrip.h"
using namespace std;
int const MAXN=256;
vector<int>nei[MAXN]={};
vector<int>ans;
vector<int>cur;
bool stk[MAXN]={},vis[MAXN]={};
void dfs(int u,int p=-1)
{
    cur.push_back(u);
    bool w=0;
    stk[u]=1;
    for (auto i:nei[u])
    {
        if (stk[i])
            continue;
        w=1;
        dfs(i,u);
    }
    stk[u]=0;
    if (cur.size()>ans.size())
        ans=cur;
    cur.pop_back();
}
vector<int> sol(int N)
{
    vector<int>ans;
    for (int i=0;i<N;i++)
    {
        int q=i;
        vector<int>cur;
        while(!vis[q])
        {
            vis[q]=1;
            cur.push_back(q);
            for (auto i:nei[q])
            {
                if (!vis[i])
                {
                    q=i;
                    break;
                }
            }
        }
        if (cur.size()>ans.size())
            ans=cur;
    }
    return ans;
}
vector<int> longest_trip(int N, int D)
{
    ans={};
    cur={};
    for (int i=0;i<N;i++)
        nei[i]={},vis[i]=0;
    for (int i=0;i<N;i++)
        for (int j=i+1;j<N;j++)
            if (are_connected({i},{j}))
                nei[i].push_back(j),nei[j].push_back(i);
    if (D==1)
    {
        return sol(N);
    }
    for (int i=0;i<N;i++)
        dfs(i);
    return ans;
}

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