제출 #1332935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1332935		nerrrmin	가장 긴 여행 (IOI23_longesttrip)	C++20	15 / 100	362 ms	1020 KiB

longesttrip

#include "longesttrip.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 303;
int n, d;
vector < int > g[maxn];
vector < int > path;
int used[maxn];
int is[maxn][maxn];
void dfs(int beg, vector < int >&curr)
{
    used[beg] = 1;
    if(curr.size() > path.size())
        path = curr;
    for (auto nb: g[beg])
    {
        if(used[nb])continue;
        curr.pb(nb);
        dfs(nb, curr);
        curr.pop_back();
    }
}
std::vector<int> longest_trip(int N, int D)
{
    n = N;
    d = D;
    for (int i = 0; i < n; ++ i)
    {
        for (int j = 0; j < n; ++ j)
            is[i][j] = 0;
    }
    for (int i = 0; i < n; ++ i)
        g[i].clear();
    for (int i = 0; i < n; ++ i)
    {
        for (int j = i+1; j < n; ++ j)
        {
            vector < int > from,to;
            from.pb(i);
            to.pb(j);
            if(are_connected(from, to))
            {
                g[i].pb(j);
                g[j].pb(i);
                is[i][j] = 1;
                is[j][i] = 1;
            }
        }
    }
    vector < int > ans;
    for (int st = 0; st < n; ++ st)
    {
        path.clear();
        vector < int > s;
        for (int i = 0; i < n; ++ i)
        {
            s.pb(i);
            used[i] = 0;
        }
        random_shuffle(s.begin(), s.end());
        path.pb(st);
        used[st] = 1;
        int last = st;
        while(path.size() < n)
        {
            while(s.size() && used[s.back()])s.pop_back();
            if(s.size() == 0)break;
            int op = s.back();
            used[op] = 1;
            s.pop_back();
            if(is[last][op])
            {
                path.pb(op);
                used[op] = 1;
                last = op;
            }
            else
            {
                while(s.size() && used[s.back()])s.pop_back();
                if(s.size() == 0)break;
                int mid = s.back();
                s.pop_back();
                path.push_back(mid);
                path.push_back(op);
                used[mid] = 1;
                
                
                last = op;
            }
            if(path.size() == n)return path;
        }
        if(ans.size() < path.size())ans = path;
    }

    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:61:23: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<int*, vector<int> >]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   61 |         random_shuffle(s.begin(), s.end());
      |         ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from longesttrip.cpp:3:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

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