Submission #1078798

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078798		jer033	Thousands Islands (IOI22_islands)	C++17	9.10 / 100	33 ms	6564 KiB

islands

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

int c(int a)
{
    if (a%2)
        return a-1;
    return a+1;
}

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] = 1;
    for (int i=0; i<M; i++)
    {
        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(c(cycled[0]));
            journey.push_back(cycled[1]);
            journey.push_back(c(cycled[1]));
            journey.push_back(c(cycled[0]));
            journey.push_back(cycled[0]);
            journey.push_back(c(cycled[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