Submission #736513

#	Time	Username	Problem	Language	Result	Execution time	Memory
736513		puppy	Thousands Islands (IOI22_islands)	C++17	100 / 100	286 ms	35780 KiB

islands

#include "islands.h"

#include <variant>
#include <vector>
#include <utility>
#include <functional>
#include <algorithm>
#include <iostream>
#include <set>
#include <queue>
using namespace std;
set<int> out[100005];
set<int> in[100005];
bool removed[100005];
bool visited[100005];
bool cycle[100005];
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++) {
            out[U[i]].insert(i);
            in[V[i]].insert(i);
        }
        queue<int> q;
        for (int i = 0; i < N; i++) {
            if (out[i].empty()) {
                removed[i] = true;
                q.push(i);
            }
        }
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            if (cur == 0) return false;
            for (int k:in[cur]) {
                out[U[k]].erase(k);
                if (!removed[U[k]] && out[U[k]].empty()) {
                    removed[U[k]] = true;
                    q.push(U[k]);
                }
            }
            in[cur].clear();
        }
        int st = 0;
        vector<int> v;
        while (1) {
            if (out[st].size() >= 2) break;
            else if (removed[st] || out[st].empty()) return false;
            queue<int> q;
            q.push(st);
            removed[st] = true;
            while (!q.empty()) {
                int cur = q.front(); q.pop();
                for (int k:in[cur]) {
                    if (removed[U[k]]) continue;
                    out[U[k]].erase(k);
                    if (out[U[k]].empty()) {
                        removed[U[k]] = true;
                        q.push(U[k]);
                    }
                }
            }
            v.push_back(*out[st].begin());
            st = V[v.back()];
        }
        for (int i = 0; i < N; i++) {
            if (removed[i]) continue;
            vector<int> to_remove;
            auto it = ++out[i].begin();
            if (i == st) ++it;
            for (;it != out[i].end(); ++it) to_remove.push_back(*it);
            for (int k:to_remove) out[i].erase(k);
        }
        visited[st] = true;
        vector<int> t1;
        t1.push_back(*out[st].begin());
        int _end = -1;
        while (1) {
            int cur = V[t1.back()];
            visited[cur] = true;
            int nxt = *out[cur].begin();
            t1.push_back(nxt);
            if (visited[V[nxt]]) {
                _end = V[nxt];
                break;
            }
            else {
                cur = V[nxt];
            }
        }
        vector<int> str, cyc;
        bool flag = false;
        for (int i:t1) {
            flag |= U[i] == _end;
            if (flag) cyc.push_back(i);
            else str.push_back(i);
        }
        for (int i:cyc) cycle[U[i]] = true;
        fill(visited, visited + 100005, false);
        vector<int> t2;
        visited[st] = true;
        t2.push_back(*++out[st].begin());
        _end = -1;
        while (1) {
            int cur = V[t2.back()];
            if (cycle[cur]) {
                vector<int> ans;
                for (int i:v) ans.push_back(i);
                for (int i:str) ans.push_back(i);
                for (int i:cyc) ans.push_back(i);
                reverse(str.begin(), str.end());
                for (int i:str) ans.push_back(i);
                for (int i:t2) ans.push_back(i);
                int pos = 0;
                while (V[cyc[pos]] != cur) pos++;
                for (int i = pos; i > pos - (int)cyc.size(); i--) {
                    ans.push_back(cyc[(i + (int)cyc.size()) % cyc.size()]);
                }
                reverse(t2.begin(), t2.end());
                for (int i:t2) ans.push_back(i);
                reverse(v.begin(), v.end());
                for (int i:v) ans.push_back(i);
                return ans;
            }
            visited[cur] = true;
            int nxt = *out[cur].begin();
            t2.push_back(nxt);
            if (visited[V[nxt]]) {
                _end = V[nxt];
                break;
            }
            else {
                cur = V[nxt];
            }
        }
        vector<int> str2, cyc2;
        flag = false;
        for (int i:t2) {
            flag |= U[i] == _end;
            if (flag) cyc2.push_back(i);
            else str2.push_back(i);
        }
        vector<int> ans;
        for (int i:v) ans.push_back(i);
        for (int i:str) ans.push_back(i);
        for (int i:cyc) ans.push_back(i);
        reverse(str.begin(), str.end());
        for (int i:str) ans.push_back(i);
        for (int i:str2) ans.push_back(i);
        for (int i:cyc2) ans.push_back(i);
        reverse(str2.begin(), str2.end());
        for (int i:str2) ans.push_back(i);
        reverse(str.begin(), str.end());
        for (int i:str) ans.push_back(i);
        reverse(cyc.begin(), cyc.end());
        for (int i:cyc) ans.push_back(i);
        reverse(str.begin(), str.end());
        for (int i:str) ans.push_back(i);
        reverse(str2.begin(), str2.end());
        for (int i:str2) ans.push_back(i);
        reverse(cyc2.begin(), cyc2.end());
        for (int i:cyc2) ans.push_back(i);
        reverse(str2.begin(), str2.end());
        for (int i:str2) ans.push_back(i);
        reverse(v.begin(), v.end());
        for (int i:v) ans.push_back(i);
        return ans;
}

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