제출 #1078758

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1078758		jer033	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	24 ms	6956 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
#include <variant>
#include <vector>
using namespace std;
using pii = pair<int, int>;

std::variant<bool, std::vector<int>> find_journey(int N, int M, std::vector<int> U, std::vector<int> V) {

    vector<vector<pii>> edges(N);
    vector<int> deg(N, 0);
    deg[0]++;
    for (int i=0; i<M; i+=2)
    {
        int u = U[i];
        int v = V[i];
        edges[u].push_back({v, i});
        edges[v].push_back({u, i+1});
        deg[u]++;
        deg[v]++;
    }

    vector<int> parent(N, -2);
    vector<int> parent_canoe(N, -1);
    queue<int> visitlist;
    parent[0] = -1;
    visitlist.push(0);
    while (!visitlist.empty())
    {
        int k = visitlist.front();
        visitlist.pop();
        if (deg[k] >= 3)
        {
            int curr = k;
            vector<int> return_home;
            while (curr!=0)
            {
                return_home.push_back(parent_canoe[curr]);
                curr = parent[curr];
            }
            int ban = parent_canoe[k];
            vector<int> cycled;
            for (pii choice: edges[k])
            {
                int y = choice.second;
                if (y!=ban)
                    cycled.push_back(y);
            }

            vector<int> journey;
            
            int ss = return_home.size();
            for (int i=ss-1; i>=0; i--)
                journey.push_back(return_home[i]);
            journey.push_back(cycled[0]);
            journey.push_back(cycled[0]^1);
            journey.push_back(cycled[1]);
            journey.push_back(cycled[1]^1);
            journey.push_back(cycled[0]^1);
            journey.push_back(cycled[0]);
            journey.push_back(cycled[1]^1);
            journey.push_back(cycled[1]);
            for (int i=0; i<ss; i++)
                journey.push_back(return_home[i]);
            return journey;
        }
        for (pii edge: edges[k])
        {
            int neigh = edge.first;
            int canoe = edge.second;
            if (parent[neigh] == -2)
            {
                parent[neigh] = k;
                parent_canoe[neigh] = canoe;
                visitlist.push(neigh);
            }
        }
    }

    return false;

}

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