Submission #736366

#	Time	Username	Problem	Language	Result	Execution time	Memory
736366		puppy	Thousands Islands (IOI22_islands)	C++17	1.75 / 100	1116 ms	1050956 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include <functional>
using namespace std;
vector<pair<int, int>> adj[1005];
int ot(int k)
{
    return k % 2 ? (k-1) : (k+1);
}
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; i++) {
            adj[U[i]].push_back(make_pair(V[i], i));
        }
        if (adj[0].size() >= 2) {
            int on = adj[0][0].second, to = adj[0][1].second;
            return vector<int>({on, ot(on), to, ot(to), ot(on), on, ot(to), to});
        }
        else if (adj[0].empty()) return false;
        else {
            vector<int> crs;
            crs.push_back(adj[0][0].second);
            int cur = adj[0][0].first;
            while (1) {
                if (adj[cur].size() == 1) return false;
                else if (adj[cur].size() == 2) {
                    crs.push_back(ot(adj[cur][0].second) == crs.back() ? adj[cur][1].second : adj[cur][0].second);
                }
                else {
                    vector<int> v;
                    for (int i = 0; i < 3; i++) {
                        if (ot(adj[cur][i].second) == crs.back()) continue;
                        else {
                            v.push_back(adj[cur][i].second);
                            if (v.size() == 2) break;
                        }
                    }
                    vector<int> ans;
                    for (int i:crs) ans.push_back(i);
                    ans.push_back(v[0]);
                    ans.push_back(ot(v[0]));
                    ans.push_back(v[1]);
                    ans.push_back(ot(v[1]));
                    ans.push_back(ot(v[0]));
                    ans.push_back(v[0]);
                    ans.push_back(ot(v[1]));
                    ans.push_back(v[1]);
                    for (int i = (int)crs.size() - 1; i >= 0; i--) ans.push_back(crs[i]);
                    return ans;
                }
            }
        }
}

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