제출 #736413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
736413		puppy	수천개의 섬 (IOI22_islands)	C++17	24 / 100	40 ms	5724 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include <utility>
#include <functional>
#include <algorithm>
#include <iostream>
using namespace std;
vector<pair<int, int>> adj[1005];
int ot(int k)
{
    return k % 2 ? (k-1) : (k+1);
}
bool visited[100005]; //간선 방문 체크
bool vsv[1005]; //정점 방문 체크
bool visited2[1005];
std::variant<bool, std::vector<int>> find_journey(
    int N, int M, std::vector<int> U, std::vector<int> V) {
        for (int i = 0; i < M / 2; i++) {
            adj[U[2*i]].push_back(make_pair(V[2*i], i));
        }
        vector<int> vc;
        int _end = -1;
        function<void(int)> dfs = [&](int v)
        {
            vsv[v] = true;
            visited2[v] = true;
            for (pair<int, int> p:adj[v]) {
                if (visited[p.second]) continue;
                visited[p.second] = true;
                vc.push_back(p.second);
                if (vsv[p.first]) {
                    _end = p.first;
                    return;
                }
                if (visited2[p.first]) {
                    vc.pop_back();
                    visited[p.second] = false;
                    continue;
                }
                dfs(p.first);
                if (_end != -1) return;
                visited[p.second] = false;
                vc.pop_back();
            }
            vsv[v] = false;
        };
        dfs(0);
        if (_end == -1) {
            return false;
        }
        vector<int> v1, v2;
        bool flag = false;
        for (int i = 0; i < (int)vc.size(); i++) {
            if (U[2*vc[i]] == _end) flag = true;
            if (flag) v2.push_back(vc[i]);
            else v1.push_back(vc[i]);
        }
        vector<int> ans;
        for (int i:v1) ans.push_back(2*i);
        for (int i:v2) ans.push_back(2*i);
        for (int i:v2) ans.push_back(2*i+1);
        reverse(v2.begin(), v2.end());
        for (int i:v2) ans.push_back(2*i);
        for (int i:v2) ans.push_back(2*i+1);
        reverse(v1.begin(), v1.end());
        for (int i:v1) ans.push_back(2*i);
        return ans;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 21
• Subtask 4: 24 / 24
• Subtask 5: 0 / 45