Submission #1236913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236913		countless	Thousands Islands (IOI22_islands)	C++20	5 / 100	77 ms	16196 KiB

islands

#include "islands.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

variant<bool, vector<int>> find_journey(int N, int M, vector<int> U, vector<int> V) {
    vector<vector<pair<int, int>>> adj(N), rev(N);
    vector<int> out(N);
    map<pair<int, int>, int> loc;
    for (int i = 0; i < M; i++) {
        adj[U[i]].emplace_back(V[i], i);
        rev[V[i]].emplace_back(U[i], i);
        out[U[i]]++;
        loc[{U[i], V[i]}] = i;
    }

    // FIND ANY EDGE WITH DEGREE 2
    int start = -1;

    vector<int> ans;
    if (out[0] >= 2) {
        start = 0;
        int left = adj[0][0].first;
        int right = adj[0][1].first;

        int a, b, c, d;
        a = loc[{0, left}], b = loc[{left, 0}];
        c = loc[{0, right}], d = loc[{right, 0}];
        
        ans = {a, b, c, d, b, a, d, c};
        return ans;
    }

    if (start == -1) {
        vector<bool> vis(N);
        vector<int> par(N, -1);
        queue<int> q;
        vis[0] = true;
        q.emplace(0);

        while (!q.empty()) {
            auto u = q.front(); q.pop();

            for (auto &[v, i] : adj[u]) {
                if (!vis[v]) {
                    par[v] = u;
                    vis[v] = true;
                    q.emplace(v);
                    if (out[v] >= 3) {
                        start = v;
                        break;
                    }
                }
            }
        }

        if (start == -1) return false;

        int at = start;
        vector<int> path;
        while (at != -1) {
            // cerr << at sp par[at] << endl;
            path.push_back(at);
            at = par[at];
        }

        int m = path.size();
        for (int i = m-1; i > 1; i--) {
            int u = path[i], v = path[i-1];
            ans.push_back(loc[{u, v}]);
        }

        vector<int> cands;
        for (int i = 0; i < adj[start].size(); i++) {
            if (adj[start][i].first == par[start]) continue;
            cands.push_back(adj[start][i].first);
        }
        // cerr << "here" sp start sp adj[start].size() << endl;

        int left = cands[0], right = cands[1];
        int a, b, c, d;
        a = loc[{start, left}], b = loc[{left, start}];
        c = loc[{start, right}], d = loc[{right, start}];

        vector<int> temp = {a, b, c, d, b, a, d, c};
        for (auto &x : temp) ans.push_back(x);

        for (int i = 0; i < m-1; i++) {
            int u = path[i], v = path[i+1];
            ans.push_back(loc[{u, v}]);
        }

        return ans;
    }

    return false;
}

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